什么是动态规划
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
用斐波那契数列来讲解动态规划的五步曲
问题描述：
斐波那契数列定义如下：
- ( F(0) = 0 )
- ( F(1) = 1 )
- ( F(n) = F(n-1) + F(n-2) ) （当 ( n \geq 2 ) 时）
求第 ( n ) 项的值。
五步解决动态规划问题：
1. 确定 dp 数组（dp table）以及下标的含义
定义 ( dp[i] ) 为斐波那契数列第 ( i ) 项的值。
2. 确定递推公式
根据斐波那契数列的定义，有：
[
dp[i] = dp[i-1] + dp[i-2]
]
3. dp 数组如何初始化
- ( dp[0] = 0 )（斐波那契数列第 0 项）。
- ( dp[1] = 1 )（斐波那契数列第 1 项）。
4. 确定遍历顺序
从小到大遍历，即从 ( i = 2 ) 开始，依次计算 ( dp[2], dp[3], \dots, dp[n] )。
5. 举例推导 dp 数组
假设 ( n = 5 )，那么：
- 初始化：( dp[0] = 0, dp[1] = 1 )
- 计算：
- ( dp[2] = dp[1] + dp[0] = 1 + 0 = 1 )
- ( dp[3] = dp[2] + dp[1] = 1 + 1 = 2 )
- ( dp[4] = dp[3] + dp[2] = 2 + 1 = 3 )
- ( dp[5] = dp[4] + dp[3] = 3 + 2 = 5 )
最终，( dp[5] = 5 )。
C++ 实现代码
#include <iostream>
#include <vector>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n; // 边界情况
vector<int> dp(n + 1); // 定义 dp 数组
dp[0] = 0; // 初始化 dp[0]
dp[1] = 1; // 初始化 dp[1]
for (int i = 2; i <= n; i++) { // 从小到大遍历
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]; // 返回 dp[n]
}
int main() {
int n;
cout << "请输入 n: ";
cin >> n;
cout << "斐波那契数列第 " << n << " 项是: " << fibonacci(n) << endl;
return 0;
}
优化版（降低空间复杂度）
由于只用到最近两个状态，可以优化为 ( O(1) ) 空间复杂度：
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n; // 边界情况
int prev1 = 0, prev2 = 1; // 定义两个变量存储前两项
int curr;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2; // 当前项等于前两项之和
prev1 = prev2; // 更新 prev1 和 prev2
prev2 = curr;
}
return curr; // 返回最终结果
}
int main() {
int n;
cout << "请输入 n: ";
cin >> n;
cout << "斐波那契数列第 " << n << " 项是: " << fibonacci(n) << endl;
return 0;
}
