动态规划初步

动态规划入门：记下答案，不再重复计算

你有没有遇到过这样的数学题：小明爬楼梯，每次可以跨1级或2级，爬上10级台阶一共有多少种不同的走法？如果你一个一个地数，会数到头晕。但如果你发现一个规律——走到第10级的方法数，等于走到第9级的方法数加上走到第8级的方法数（因为最后一步要么从第9级跨1级，要么从第8级跨2级），那么你就能轻松算出来。动态规划（Dynamic Programming，简称 DP）就是一种专门解决这类问题的思路：把一个大问题拆成几个小问题，记下每个小问题的答案，然后直接用它们来拼出大问题的答案，避免重复计算。

1. 动态规划的关键概念：状态、状态转移、边界

动态规划通常用一张表格（比如数组）来记录答案，每个格子代表一个“状态”，状态就是一个小问题的结果。从最简单的小问题开始，逐步推出更复杂的问题。

• 状态：比如爬楼梯问题中，“走到第 i 级台阶有多少种方法”就是一个状态，我们用 dp[i] 表示。
• 边界：最开始的几个最简单状态。例如第1级台阶只有1种走法（跨1级），第2级台阶有2种走法（1+1 或 2）。
• 状态转移方程：描述怎样从之前的状态推出新状态。爬楼梯：dp[i] = dp[i-1] + dp[i-2]，因为最后一步要么从 i-1 跨1级，要么从 i-2 跨2级。

生活中的例子：你每个月的零花钱是100元，你想买两个玩具：一个20元，一个35元。如果你想知道“一共有多少种买法”，其实也可以看成动态规划问题——把零花钱当作台阶，每次花掉一定的钱就像跨台阶。

2. 斐波那契数列——动态规划最简单的演示

斐波那契数列的定义是：前两个数都是1，后面的每一个数等于它前面两个数之和。即：
1, 1, 2, 3, 5, 8, 13, 21, ...
这和爬楼梯问题一模一样。

直接递归（不推荐）：如果写一个递归函数，比如 fib(5) 会调用 fib(4) 和 fib(3)，而 fib(4) 又会调用 fib(3) 和 fib(2)……你会发现 fib(3) 被算了两次，fib(2) 被算了更多次。这样当 n 很大时，速度会慢得像蜗牛。

动态规划（推荐）：用一个数组 dp 把算过的结果存起来，从小到大依次计算。

#include <iostream>
using namespace std;

int main() {
    int n = 10;                // 求第10个斐波那契数
    int dp[100] = {0};         // 用来存储答案的数组，初始化为0
    dp[1] = 1;                 // 第1项是1
    dp[2] = 1;                 // 第2项是1
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 用前面两个算好的结果
    }
    cout << "第" << n << "项是：" << dp[n] << endl;
    return 0;
}

运行这个程序，它会输出 第10项是：55。注意我们只用了 dp[1] 到 dp[10]，数组开到了 100 足够用。

为什么叫“动态”？ 因为我们在循环中一个一个地“动”着计算，而规划就是事先安排好计算顺序。

3. 爬楼梯问题的完整代码

现在我们用动态规划解决真正的爬楼梯问题：假设有 n 级台阶（n 是正整数），每次可以走1级或2级，求有多少种不同的走法。

#include <iostream>
using namespace std;

int main() {
    int n = 10;                    // 台阶数量
    int dp[100] = {0};             // dp[i]表示走到第i级的方法数
    dp[0] = 1;                     // 起点（地面）算1种方法：不动
    dp[1] = 1;                     // 走到第1级只有1种：跨1级
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 要么从i-1跨1，要么从i-2跨2
    }
    cout << "爬到第" << n << "级台阶共有" << dp[n] << "种走法" << endl;
    return 0;
}

运行后输出：爬到第10级台阶共有89种走法。你可以手动验证前几级：

• 1级：1种
• 2级：2种（1+1 或 2）
• 3级：3种（1+1+1, 1+2, 2+1）
• ……

4. 新手容易犯的错误

• 数组越界：如果 n 很大，比如 n=100，但数组只开了 dp[100]，那么 dp[100] 是允许的（下标0~99），但你要用到 dp[100]？实际上 dp[100] 是第101个元素，会越界。保险做法：数组大小比 n 大一点，比如 dp[n+2]。
• 忘记边界条件：比如忘记设 dp[0] 或 dp[1]，然后循环从 i=2 开始，dp[2] 会用到未初始化的 dp[0] 和 dp[1]，导致随机数。一定要先设好边界。
• 递推方向搞反：动态规划是从小到大（从边界开始）计算，如果从大到小算，用到的结果还没算出来，就会出错。循环要从小的 i 开始。
• 把状态含义弄混：比如爬楼梯问题中，有人会把 dp[i] 定义为“前 i 级的总方法”，但那样递推关系会复杂。先想清楚状态代表什么。

5. 完整示例：小明买零食

小明每天放学后都会用零花钱买零食。他每次只能买 1 种零食：要么一个 2 元的棒棒糖，要么一个 3 元的巧克力棒。如果小明今天带了 10 元，他想把钱全部花完，有多少种不同的购买顺序？（比如 2+2+2+2+2 是一种，2+2+3+3 是另一种。）

这和爬楼梯问题几乎一样，只是每次走的步数变成了 2 或 3。状态 dp[i] 表示凑成 i 元的不同顺序数。转移方程：dp[i] = dp[i-2] + dp[i-3]。边界：dp[0] = 1（不买也是一种顺序）；dp[1] = 0（因为最小的零食是2元，1元凑不出来）。我们来写代码：

#include <iostream>
using namespace std;

int main() {
    int money = 10;              // 总钱数
    int dp[100] = {0};           // dp[i]表示凑成i元的顺序数
    dp[0] = 1;                   // 0元只有一种顺序：什么都不买
    for (int i = 1; i <= money; i++) {
        int ways = 0;            // 先假设没有方法
        if (i >= 2) {
            ways = ways + dp[i-2];  // 如果买棒棒糖，剩下的 i-2 元有多少顺序
        }
        if (i >= 3) {
            ways = ways + dp[i-3];  // 如果买巧克力，剩下的 i-3 元有多少顺序
        }
        dp[i] = ways;
    }
    cout << "用10元买零食，一共有" << dp[money] << "种不同的顺序" << endl;
    return 0;
}

输出：用10元买零食，一共有7种不同的顺序。你可以手动枚举一下：2+2+2+2+2, 2+2+3+3, 2+3+2+3, 2+3+3+2, 3+2+2+3, 3+2+3+2, 3+3+2+2。正好7种。

6. 相关指引

学会了最简单的动态规划后，你可以试试更难的问题：

• 01背包问题：你有N件物品，每件有重量和价值，书包容量有限，怎么装价值最大？
• 最长上升子序列：在一个数列中，找出一段递增的序列（可以不连续），使它的长度最长。
• 数字三角形：从顶部到底部，每次只能向下或右下方走，求路径上的数字和最大。

动态规划的核心就是记住答案，避免重复计算。只要你能把大问题拆成小问题，并且小问题之间有重复，就可以用动态规划。多用生活中的例子练习，你很快就能掌握这个强大的工具。