中等C++6 分钟2,261 字

动态规划的基本思路

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

你有没有遇到过这样的问题:要计算一个很大的数字,比如爬楼梯有多少种走法,或者买东西有多少种付钱方式,如果从头开始一个个枚举,会特别慢,而且容易算错。这时候,聪明的做法不是“硬算”,而是把大问题拆成一个个小问题,记住每个小问题的答案,以后用到时直接拿过来,不用再算一遍​​。这就是动态规划(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. 计算顺序:从小往大递推

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


新手容易犯的错误

学习动态规划时,下面几个坑要注意:

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

完整可运行的代码示例

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

cpp
#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]。

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


相关知识点指引

动态规划是信息学竞赛中非常核心的方法,学会最基本的“爬楼梯”后,你可以继续学习:

  • 斐波那契数列​​:其实就是爬楼梯的变形(f[1]=1, f[2]=1,转移一样)。
  • 背包问题​​:比如“01背包”,用动态规划选择物品使总价值最大。
  • 最长公共子序列​​:比较两个字符串的相似度。
  • 区间动态规划​​:比如合并石子、括号匹配等。

掌握了基本思路后,你会发现很多问题都可以用“定义状态、写转移、定边界、从小推到大”的思路来解决。就像搭积木,把一个个小问题拼起来,就能解决很大的问题!

同类知识点