新网网站,网线制作排序,网站导航栏制作教程,怎样选择网站的关键词动态规划:
动态规划的基本思想是#xff1a;将原问题拆分为若干子问题#xff0c;自底向上的求解。是自底向上的求解#xff0c;即是先计算子问题的解#xff0c;再得出原问题的解。 思路: 创建一个数组#xff0c;大小为n1#xff0c;用于存储斐波那契数列的值。数组的…动态规划:
动态规划的基本思想是将原问题拆分为若干子问题自底向上的求解。是自底向上的求解即是先计算子问题的解再得出原问题的解。 思路: 创建一个数组大小为n1用于存储斐波那契数列的值。数组的第i个元素对应斐波那契数列的第i项。 初始化数组的前两个元素即F(0) 0F(1) 1。 从i2开始迭代计算出第i项的值即F(i) F(i-1) F(i-2)。这个值可以直接由数组中的前两个元素得到所以不需要进行额外的函数调用。 循环结束后数组中的最后一个元素就是斐波那契数列的第n项。 代码:
#include iostream
#include vector// 定义一个函数使用动态规划求解斐波那契数列的第n项
int fibonacci_dp(int n) {// 处理基本情况如果n为0或1直接返回n因为F(0)0F(1)1if (n 1) {return n;}// 创建一个整型向量fib大小为n1用以存储斐波那契数列的每一项std::vectorint fib(n 1);// 初始化斐波那契数列的前两项fib[0] 0; // 第0项设置为0fib[1] 1; // 第1项设置为1// 使用循环从第2项开始计算斐波那契数列直到第n项for (int i 2; i n; i) {// 根据斐波那契数列的定义第i项是前两项之和fib[i] fib[i - 1] fib[i - 2];}// 循环结束后fib[n]中存储的是斐波那契数列的第n项return fib[n];
}// 主函数
int main() {int n;// 提示用户输入要计算的斐波那契数列的项数nstd::cout Enter the value of n: ;std::cin n; // 读取用户输入的n// 调用fibonacci_dp函数计算第n项的斐波那契数并将结果存储在result中int result fibonacci_dp(n);// 输出计算得到的斐波那契数std::cout Fibonacci number is: result std::endl;// 主函数返回0表示程序正常结束return 0;
}
