动态规划
掌握DP核心思想、常见模型及其高频应用
90%
📝 动态规划基本原理
🧩 经典DP模型
🌟 经典例题详解
💡 练习题与参考答案
动态规划基本原理
动态规划（DP）解决具有最优子结构和重叠子问题的问题，核心步骤：
- 定义状态：确定DP数组/表的含义（如dp[i]表示问题规模为i的解）
- 状态转移方程：找出状态之间的递推关系（如dp[i] = f(dp[i-1], dp[i-2], ...)）
- 初始化：设置边界条件（如dp[0], dp[1]的初值）
- 计算顺序：通常从小到大，确保计算当前状态时所依赖的状态已计算完毕
// 斐波那契数列的DP实现
int fibDP(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0; dp[1] = 1; // 初始化
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
}
return dp[n];
}
// 空间优化版本
int fibDP2(int n) {
if (n <= 1) return n;
int a = 0, b = 1; // dp[0], dp[1]
for (int i = 2; i <= n; ++i) {
int c = a + b; // dp[i]
a = b; b = c; // 滚动更新
}
return b;
}