掌握动态规划（Dynamic Programming）

动态规划的基本步骤

使用动态规划解决问题通常遵循以下四个步骤：

1. 定义状态（State）：明确 dp[i] 或 dp[i][j] 表示什么含义。
2. 找出状态转移方程（Recurrence Relation）：如何从已知状态推导出新状态。
3. 确定初始条件（Base Case）：最简单的情况，如 dp[0]、dp[1] 等。
4. 确定遍历顺序并计算结果。

经典例子：斐波那契数列

斐波那契数列是最简单的动态规划入门题。数列定义如下：

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) （当 n ≥ 2）

如果用普通递归实现，时间复杂度是指数级的，因为存在大量重复计算。而使用动态规划，我们可以用 O(n) 的时间完成。

C++ 动态规划实现：

#include <iostream>#include <vector>using namespace std;int fib(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 main() {    int n = 10;    cout << "Fibonacci(" << n << ") = " << fib(n) << endl;    return 0;}  

这段代码展示了典型的自底向上（Bottom-up）动态规划写法。我们用一个数组 dp 保存中间结果，避免重复计算。

进阶案例：爬楼梯问题

假设你正在爬一个有 n 阶的楼梯。每次你可以爬 1 阶或 2 阶。问有多少种不同的方法可以爬到楼顶？

这个问题其实和斐波那契数列完全一样！因为到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数。

int climbStairs(int n) {    if (n <= 2) return n;        int prev2 = 1, prev1 = 2, curr;    for (int i = 3; i <= n; ++i) {        curr = prev1 + prev2;        prev2 = prev1;        prev1 = curr;    }    return curr;}  

注意：这里我们甚至不需要整个 dp 数组，只需保存前两个状态即可，空间复杂度从 O(n) 优化到 O(1)。这是动态规划常见的空间优化技巧。

常见 DP 问题类型

掌握了基本思想后，你可以尝试以下几类经典问题：

• 线性 DP：如最长递增子序列（LIS）、最大子数组和（Kadane 算法）
• 背包问题：0-1 背包、完全背包等
• 区间 DP：如矩阵链乘法、石子合并
• 树形 DP：在树结构上进行状态转移

学习建议

要真正掌握DP算法详解，光看理论是不够的。建议你：

1. 动手写代码，哪怕是最简单的例子。
2. 画状态转移图，帮助理解 dp[i] 如何由其他状态推出。
3. 多刷 LeetCode 上的 DP 题目，从 Easy 开始。
4. 总结模板，比如“一维 DP 模板”、“二维 DP 模板”。

结语

动态规划虽然一开始看起来有点抽象，但只要你坚持练习，很快就能发现它的规律和美感。希望这篇C++算法教程能成为你 DP 学习之路的起点。记住：所有高手，都是从第一个 dp[0] 开始的！

加油！你离掌握动态规划，只差一次动手实践的距离。