动态规划入门：把大问题拆成小问题，记住答案就能变快

动态规划（Dynamic Programming，简称DP）听起来有点高深，但它其实就像你平时做作业用到的一个聪明方法：遇到一个复杂的大题目，先把它拆成几个简单的小步骤，每做完一小步就把答案记在草稿纸上，这样后面用到这个答案时直接查看，不用再算一遍。这种 “拆大变小、记下答案” 的思想，就是动态规划的核心。

动态规划特别适合解决这样一类问题：大问题可以拆成几个规模更小、结构相似的小问题，而且这些小问题之间会重复出现。比如计算斐波那契数列、爬楼梯、找零钱、最短路径等等。如果我们不记录中间结果，用递归硬算会算很多次重复的步骤，而动态规划通过一个表格（通常是数组）把每一步的答案存下来，就能大大节省时间。

状态和状态转移：给每一步起个名字，并找到它和前一步的关系

动态规划里有两个最重要的概念：状态 和 状态转移方程。

• 状态：表示某个子问题的答案，通常用 dp[i] 表示“规模为 i 时的答案”。
• 状态转移方程：描述如何从小状态得到大状态，比如 dp[i] = dp[i-1] + dp[i-2]。

就像你从1楼爬到10楼，每次可以走1级或2级台阶。我们把“到达第 i 级台阶的走法种数”定义为状态 dp[i]。那么要到达第10级，要么从第8级跨2步，要么从第9级跨1步，所以 dp[10] = dp[8] + dp[9]。这就是状态转移方程。继续拆下去，直到最简单的1级（只有1种走法，即 dp[1]=1）和2级（dp[2]=2，可以一次1级+一次1级，或者一次2级）。

动态规划三步走

不管题目怎么变，解决动态规划问题通常就三步：

1. 定义状态：想清楚 dp[i] 表示什么。比如“爬到第 i 级台阶有多少种方法”。
2. 找到状态转移方程：找出大状态和小状态之间的关系。比如 dp[i] = dp[i-1] + dp[i-2]。
3. 确定初始值：最小的状态（边界）是多少。比如 dp[1]=1, dp[2]=2（如果 i 从1开始）。

把这三步想清楚了，剩下的就是用循环从小的状态一直推到大的状态。

生活中的动态规划：存零花钱的故事

假设你每天把零花钱存进储蓄罐，但父母规定：第一天只能存1元，第二天可以存1元或2元，从第三天开始，每天能存的钱数等于前两天存的钱数之和。你想知道第10天一共存了多少钱？（其实这就是斐波那契数列）

用动态规划的思想：

• 定义状态 dp[i] 表示第 i 天结束时储蓄罐里的总钱数。
• 状态转移：第 i 天的钱 = 第 i-1 天的钱 + 第 i-2 天的钱（因为每天只能存前两天的和）。
• 初始值：第1天有1元（dp[1]=1），第2天有1+1=2元（dp[2]=2）。

这样算下去，第10天的钱数就是斐波那契数列的第10项（但注意斐波那契从0开始的话第10项是55，这里从1开始第10项是89）。

这个例子和爬楼梯本质一模一样，只是把“走法种数”换成了“钱数”。

新手常见的错误

虽然动态规划思想不复杂，但写代码时容易掉进下面几个坑：

1. 忘记定义清楚状态：比如把 dp[i] 定义成“爬到第 i 级台阶的方法数”，后面却用它来表示“步数”，导致逻辑混乱。
2. 状态转移方程写错：比如爬楼梯中 dp[i] = dp[i-1] + dp[i-2] 写成了 dp[i] = dp[i-1] + 1，或者漏掉一种情况。
3. 初始值不对：比如 dp[0] 和 dp[1] 没给对，导致后面的结果全错。爬楼梯中通常 dp[0]=1（理解为站在地上不爬也算一种），dp[1]=1。
4. 数组越界：比如循环从 i=2 开始，但 dp[i-2] 要求 i>=2，如果 n=1 还没处理就直接访问 dp[1] 会报错。一定要先处理边界情况。
5. 以为动态规划只能求数量：其实它还能求最大值、最小值、路径方案等，关键看状态定义。

完整可运行的代码示例：爬楼梯问题

下面我们用动态规划计算爬10级台阶有多少种走法（每次走1或2级）。这个例子和斐波那契一模一样，但更贴近生活。

def climb_stairs_dp(n):
    """
    计算爬 n 级台阶的走法数，每次可以走1级或2级。
    动态规划解法。
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    # step_count[i] 表示爬到第 i 级台阶的走法种数
    step_count = [0] * (n + 1)   # 下标0到n，step_count[0]暂时不用
    step_count[1] = 1            # 到第1级只有1种走法
    step_count[2] = 2            # 到第2级有2种走法：1+1 或 2
    # 从第3级开始，每级的走法数 = 前两级之和
    for i in range(3, n + 1):
        step_count[i] = step_count[i-1] + step_count[i-2]
    return step_count[n]

# 测试：10级台阶有多少种走法？
print(climb_stairs_dp(10))  # 输出 89

运行结果：89
你可以试着手动验证：到第3级是3种，第4级是5种，第5级是8种……这其实就是斐波那契数列从1,2开始。

再举一个例子：格子游戏（网格路径）

小明要从超市门口（左上角）走到学校（右下角），只能向右或向下走，请问有多少条不同的路径？
这种问题也可以用动态规划：把 dp[i][j] 定义为“到达第 i 行第 j 列的走法数”。
状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]（因为只能从上面或左边过来）。
初始值：第一行和第一列的格子都只有1种走法（一直向右或一直向下）。

def unique_paths(rows, cols):
    """
    计算从网格左上角到右下角有多少条不同路径，只能向右或向下。
    rows: 行数，cols: 列数
    """
    # dp[r][c] 表示到达第 r 行第 c 列的走法数
    dp = [[0] * cols for _ in range(rows)]

    # 第一行：只能从左边来，所以都是1种
    for c in range(cols):
        dp[0][c] = 1
    # 第一列：只能从上边来，所以都是1种
    for r in range(rows):
        dp[r][0] = 1

    # 填充其余格子
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]

    return dp[rows-1][cols-1]  # 返回右下角的答案

# 测试一个3行3列的网格（共9个格子），从左上到右下有多少条路径？
print(unique_paths(3, 3))  # 输出 6

这个例子和爬楼梯非常相似，只是从一维变成了二维，核心思想完全一样：大问题拆成小问题，记住小问题的答案。

相关知识点指引

动态规划是一个庞大的家族，学会了基础思路后，你可以继续探索：

• 0/1背包问题：每个物品拿或不拿，用 dp[i][j] 表示前 i 个物品在容量 j 下的最大价值。
• 最长上升子序列（LIS）：用 dp[i] 表示以第 i 个数字结尾的最长上升子序列长度。
• 区间DP：处理像“合并石子”这类问题，用 dp[i][j] 表示区间 [i, j] 上的最优解。
• 记忆化搜索：这是动态规划的另一种写法，用递归+记忆数组，本质和递推一样。

记住：遇到一个问题时，先别急着写代码，按“三步走”思考：定义状态 → 找转移方程 → 确定初始值。多练几个经典题目，就能慢慢掌握这个“拆大变小、记住答案”的魔法了。