动态规划求解 fibonacci 数列

动态规划:

• 动态规划的基本思想是：将原问题拆分为若干子问题，自底向上的求解。
• 是自底向上的求解，即是先计算子问题的解，再得出原问题的解。

思路:

1. 创建一个数组，大小为n+1，用于存储斐波那契数列的值。数组的第i个元素对应斐波那契数列的第i项。

2. 初始化数组的前两个元素，即F(0) = 0，F(1) = 1。

3. 从i=2开始，迭代计算出第i项的值，即F(i) = F(i-1) + F(i-2)。这个值可以直接由数组中的前两个元素得到，所以不需要进行额外的函数调用。

4. 循环结束后，数组中的最后一个元素就是斐波那契数列的第n项。

代码:

#include <iostream>
#include <vector>// 定义一个函数，使用动态规划求解斐波那契数列的第n项
int fibonacci_dp(int n) {// 处理基本情况：如果n为0或1，直接返回n，因为F(0)=0，F(1)=1if (n <= 1) {return n;}// 创建一个整型向量fib，大小为n+1，用以存储斐波那契数列的每一项std::vector<int> 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;
}