动态规划的基本思路

把“大麻烦”拆成“小麻烦”——动态规划入门

你有没有遇到过这样的问题：要计算一个很大的数字，比如爬楼梯有多少种走法，或者买东西有多少种付钱方式，如果从头开始一个个枚举，会特别慢，而且容易算错。这时候，聪明的做法不是“硬算”，而是把大问题拆成一个个小问题，记住每个小问题的答案，以后用到时直接拿过来，不用再算一遍。这就是动态规划（Dynamic Programming）的核心思想。

动态规划听起来很厉害，其实它就像一位聪明的管家，在整理房间时会把东西分类放好，需要时一下子就能找到。我们做计算时，也会遇到很多重复的“小麻烦”，动态规划就是帮我们把每个小麻烦的答案记下来，以后遇到同样的麻烦，直接拿出答案，不用再算一遍。

生活中的比喻：爬楼梯

假设你要爬10级楼梯，每次可以跨1级或2级。问有多少种不同的爬法？如果你从头想到尾，会发现很乱。但聪明的做法是：要想到达第10级，必须先到第8级（然后跨2步）或第9级（然后跨1步）。所以，到第10级的爬法数 = 到第8级的爬法数 + 到第9级的爬法数。同样道理，每个台阶的爬法都可以用前面台阶的爬法算出来。我们只需要从第1级开始，一级一级往上算，并记下每个台阶的答案。

核心三要素：状态、转移方程、边界

动态规划解题需要三个关键东西，就像做一道菜需要：食材（状态）、菜谱（转移方程）和调料（边界）。

1. 状态：用变量表示“子问题”

状态就是我们要记录的小问题。比如爬楼梯问题中，我们用 f[i] 表示“爬到第 i 级台阶有多少种不同的方法”。这里的 i 是台阶编号，f[i] 的值就是方法数。

生活例子：小明每天存零花钱，他可以每天存1元或2元。问 n 天后，他有多少种不同的存钱方式？那么我们可以定义状态 f[i]：存满 i 元有多少种方式。是不是和爬楼梯很像？

2. 转移方程：相邻状态之间的关系

转移方程告诉我们怎么从小问题的答案推出大问题的答案。在爬楼梯问题中，要爬到第 i 级台阶，最后一步要么从第 i-1 级跨1步上来，要么从第 i-2 级跨2步上来。所以：

f[i] = f[i-1] + f[i-2]

这就是转移方程。

生活例子：小明要存满 i 元，最后一天他可能存1元（这样前一天有 i-1 元），也可能存2元（这样前一天有 i-2 元）。所以存满 i 元的方法数 = 存满 i-1 元的方法数 + 存满 i-2 元的方法数。和爬楼梯一模一样！

3. 边界：最简单的情况

边界就是最小的子问题，不需要再分解。比如爬楼梯：

第1级台阶：只有一种爬法（直接跨1级），所以 f[1] = 1。
第2级台阶：可以跨两次1级，或者一次跨2级，共2种，所以 f[2] = 2。

生活例子：小明存钱，存1元只有1种方式（第一天存1元）；存2元有2种方式（每天存1元，或一天存2元）。边界和爬楼梯一样。

4. 计算顺序：从小往大递推

有了状态、转移方程、边界，我们就可以从最小的状态开始，按照转移方程逐步计算出所有更大的状态。这种“从小到大的顺序”叫作递推，是动态规划最常见的实现方式。

新手容易犯的错误

学习动态规划时，下面几个坑要注意：

忘记定义边界：比如爬楼梯，如果 n=1 或 n=2，直接输出结果，否则数组会访问 f[-1] 或 f[0] 出错。
数组越界：定义数组时大小不够。比如题目说 n ≤ 100，你开 int f[50]，当 n=60 时就出错了。
递推顺序搞反：有人会写成 for (int i = n; i >= 1; i--)，从大到小算，但递推依赖前面的小状态，必须从小到大。
重复计算：如果不记录结果，用递归直接算，会重复算很多次，非常慢。动态规划就是解决这个问题的。

完整可运行的代码示例

下面是一个完整的爬楼梯程序，可以输入任意正整数 n（建议不超过 1000），输出方法数。注意方法数可能很大，这里用 long long 类型存储（可处理 n 到 90 左右，再大需要大整数）。

#include <iostream>
using namespace std;

int main() {
    int n;                 // 楼梯级数
    cin >> n;
    
    // 处理边界情况
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (n == 2) {
        cout << 2 << endl;
        return 0;
    }
    
    long long f[1005];    // 存储每个台阶的爬法数，用long long避免溢出
    f[1] = 1;             // 第1级台阶有1种方法
    f[2] = 2;             // 第2级台阶有2种方法
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];   // 递推公式
    }
    cout << f[n] << endl;      // 输出第n级的答案
    return 0;
}

运行示例：

输入：10
输出：89
输入：50
输出：20365011074

更多生活中的例子：走方格

除了爬楼梯，还有一种经典问题：走方格。比如有一个 3×3 的网格，从左上角走到右下角，每次只能向右或向下走一格，有多少种不同的走法？这个问题也可以用动态规划解决。

状态：设 dp[i][j] 表示从起点走到第 i 行第 j 列有多少种走法。
边界：第一行 dp[0][j] = 1（只能一直向右），第一列 dp[i][0] = 1（只能一直向下）。
转移方程：到达 (i, j) 只能从左边 (i, j-1) 或上边 (i-1, j) 来，所以 dp[i][j] = dp[i][j-1] + dp[i-1][j]。

这和爬楼梯的逻辑一模一样，只是变成了二维。你可以在课后试试自己写代码实现。