专题 09动态规划（入门）

9.1DP 到底在干什么：从斐波那契说起

很多教程一上来就说「DP 三要素：状态、转移、边界」，但这句话对初学者等于没说。 要理解 DP，最干净的办法是看一个你早就写过的例子——求斐波那契数列的第 n 项。

斐波那契的递归定义你一定认识：

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)      // n >= 2

照着这个定义，最朴素的写法就是直接翻译：

// 暴力递归：完全照着数学定义翻译
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);   // 每个 n 都要往下拆两次
}

为什么这个写法慢到离谱

你每次算 fib(n)，都要先算 fib(n-1) 和 fib(n-2)；而 fib(n-1) 自己又要把 fib(n-2) 和 fib(n-3) 各算一遍。 注意，fib(n-2) 被算了两次——左边那棵子树算一次，右边那棵也算一次。随着 n 变大，这种重复呈指数爆炸：

            fib(5)
          /        \
      fib(4)        fib(3)
      /    \         /    \
  fib(3)  fib(2)  fib(2)  fib(1)
  /   \    /  \    /   \
fib(2) ... 重复的子树越来越多

粗略地说，fib(n) 被调用的次数是指数级的（约为 2ⁿ 量级）。这正是 DP 要解决的第一个核心问题： 重叠子问题——同一个更小的子问题被反复求解。

第一步优化：记忆化（自顶向下）

既然 fib(n-2) 算过一次结果就是固定的，那我们算完把它存起来，下次直接取不就行了？这就是「记忆化搜索」：

// 记忆化：用一个数组把算过的答案缓存下来
int[] memo;

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];          // 算过就直接返回
    memo[n] = fib(n - 1) + fib(n - 2);         // 没算过就计算并存好
    return memo[n];
}

现在每个 fib(k) 最多被真正计算一次，整体复杂度从 2ⁿ 降到 O(n)。 思路没变（还是从大问题往小问题递归），只是「查表」替我们砍掉了重复计算。

第二步优化：自底向上填表（真正的 DP）

再退一步想：fib(n) 依赖 fib(n-1) 和 fib(n-2)，而这两个又依赖更小的。 与其从 n 往下递归，不如反过来——从 0、1 开始，一路往大里算，把每个结果填进数组：

// 自底向上：从最小的子问题开始，逐个填表
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int[] dp = new int[n + 1];   // dp[i] 表示「斐波那契第 i 项」
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // 用已经算好的小问题，推出大问题
    }
    return dp[n];
}

这就是动态规划最典型的样子：

DP 的第二个特征：最优子结构

斐波那契只是「计数」，还没涉及「最优」。DP 还有一类问题叫「求最值」，比如「爬楼梯最少花多少」「打家劫舍最多能偷多少」。 这类问题额外要求一个性质：大问题的最优解，能由小问题的最优解拼出来，这叫「最优子结构」。

举个例子：如果你想知道「偷到最后一间房的最大收益」，而你已经知道了「偷到倒数第二间的最大收益」和「偷到倒数第三间的最大收益」， 那就能直接推出答案。也就是说，全局最优 = 局部最优的某种组合。 后面这几道题，全是在「定义清楚局部最优」这件事上做文章。

9.2DP 五步法：每次都照这个顺序想

面对任何一道 DP 题，不要急着写代码。按下面五步依次想清楚，能避免 90% 的 WA（Wrong Answer）。 这五步是本章的骨架，后面每道题我都会显式地走一遍。

第 1 步：定义状态（dp[i] 到底表示什么）

这是最关键也最容易被跳过的一步。你要给 dp[i] 一句人话解释，比如：

• 「dp[i] 表示：爬到第 i 级台阶有多少种方法」
• 「dp[i] 表示：偷到第 i 间房（含）为止，最多能偷到多少钱」

怎么判断这步做对了：你能否不假思索地用一句话说清 dp[i] 的含义，而且这句话里 i 的位置是明确的？ 如果连你自己都说不清「dp[i] 是第 i 个还是前 i 个」，后面一定写错。很多 bug 的根源就是状态定义含糊。

第 2 步：写出状态转移方程

用大白话想：「要得到 dp[i]，我需要用到哪些更小的 dp 值？它们怎么组合？」

比如爬楼梯：要到第 i 级，最后一步要么从第 i-1 级跨 1 步，要么从第 i-2 级跨 2 步。 所以「到第 i 级的方法数 = 到第 i-1 级的方法数 + 到第 i-2 级的方法数」。写成：dp[i] = dp[i-1] + dp[i-2]。

怎么判断这步做对了：拿一个具体的小数字代入，比如 i=3，手动算 dp[3] 看是否等于 dp[2]+dp[1]。

第 3 步：初始化

「最小的那些子问题」的值是什么？也就是 dp 数组最前面几个（或 dp[0]、dp[1]）该填什么。 这一步最容易被漏掉，导致后面全是错的基线。

怎么判断做对了：看「转移方程里用到的最小下标」是否都已经手动赋了值。 若转移用到 dp[i-2]，那 dp[0] 和 dp[1] 必须显式初始化。

第 4 步：确定遍历顺序

是从左往右、从右往左，还是二维里先行后列？顺序必须保证「算 dp[i] 时，它依赖的那些 dp 值已经算好了」。

怎么判断做对了：看转移方程右边用到的下标，是不是都排在 i 的前面（且已经算过）。

第 5 步：举例验证

用题目给的最小例子，在纸上把 dp 数组从头填到尾，看最后一个值是不是正确答案。 这步看似笨，却是 DP 防错的最后一道闸——很多人代码写完一提交才发现初始化就错了。

9.3爬楼梯（简单，力扣 70）

简单 核心：最朴素的状态转移

题意：你每次可以爬 1 级或 2 级台阶，问爬到第 n 级共有多少种不同的方法。 比如 n = 3，有 3 种走法：1+1+1、1+2、2+1；n = 2，有 2 种：1+1、2。

思路推导

我们先想暴力：要走到第 n 级，最后一步只可能是两种——

• 你刚从第 n-1 级跨了 1 步上来；
• 你刚从第 n-2 级跨了 2 步上来。

而「到第 n-1 级的方法数」和「到第 n-2 级的方法数」是互不重叠的两类走法（最后一步步数不同）， 所以总数就是把两者相加。于是我们自然地定义了：

状态：dp[i] = 爬到第 i 级台阶的方法总数。

转移：dp[i] = dp[i-1] + dp[i-2]。

初始化：dp[1] = 1（一级只有一种走法），dp[2] = 2（1+1、2）。为统一起见也可以设 dp[0] = 1 表示「地面」，这样 dp[2] = dp[1]+dp[0] = 2 也成立。

遍历顺序很明显：从 i=3 一直算到 n，因为 dp[i] 依赖前面两项。

参考代码

class Solution {
    public int climbStairs(int n) {
        // 边界：n 很小直接返回，避免数组越界
        if (n == 1) return 1;
        if (n == 2) return 2;
        // dp[i] 表示爬到第 i 级台阶的方法数
        int[] dp = new int[n + 1];
        dp[1] = 1;          // 第 1 级：只有 1 种（走一步）
        dp[2] = 2;          // 第 2 级：1+1 或 2，共 2 种
        // 从第 3 级开始，每一级的方法数 = 前两级之和
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

空间还能再压：dp[i] 只用到前两项，所以只用两个变量滚动即可（滚动数组）：

class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int prev2 = 1;   // 相当于 dp[i-2]
        int prev1 = 2;   // 相当于 dp[i-1]
        int cur = 0;
        for (int i = 3; i <= n; i++) {
            cur = prev1 + prev2;   // dp[i] = dp[i-1] + dp[i-2]
            prev2 = prev1;         // 滚动：原来的 dp[i-1] 变成下一轮的 dp[i-2]
            prev1 = cur;           // 原来的 dp[i]   变成下一轮的 dp[i-1]
        }
        return cur;
    }
}

复杂度：时间 O(n)，每个 i 只算一次；空间 O(1)（滚动数组版）。n ≤ 45 在题目约束内，O(n) 完全够。

9.4使用最小花费爬楼梯（简单，力扣 746）

简单 核心：dp 数组长度的陷阱

题意：给你一个数组 cost，长度 n，cost[i] 表示踏上第 i 级台阶需要支付的费用。 你可以从下标 0 或下标 1 出发（起步不花钱），每步可以爬 1 级或 2 级，目标是到达「楼顶」（即下标 n，也就是数组之外的那一级）。 问最小总花费。例如 cost = [10,15,20]，从 1 出发直接跨 2 步到楼顶，花 15，是最优解。

思路推导

这道题比爬楼梯多了一个「花费」维度，而且藏着一个容易踩的坑：终点是下标 n，不是 n-1。 因为楼顶在数组之外，你从最后一级（n-1）再跨一步才到顶，而跨这最后一步本身不额外收费（收费只发生在「踏上某级」时）。

先定义状态。自然地，我们让 dp[i] 表示「踏上第 i 级台阶的最小累计花费」。 那么要踏上第 i 级，你只能从第 i-1 级跨 1 步、或从 i-2 级跨 2 步上来，并且一旦踏上 i 就要付 cost[i]：

dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

初始化：因为可以从 0 或 1 直接起步且不花钱，所以踏上第 0 级的最小花费就是 cost[0]，踏上第 1 级就是 cost[1]：

dp[0] = cost[0]
dp[1] = cost[1]

终点：楼顶在 n，从 n-1 跨一步或 n-2 跨两步都能到，且到顶不再收费，所以答案 = min(dp[n-1], dp[n-2])。

这里 dp 数组长度要开 n（下标 0..n-1），因为楼顶我们不存花费，只在最后取 min。 如果你把 dp 开成 n+1 并把 dp[n] 也作为状态存「到楼顶的花费」，也行，但容易和 cost 对齐错位——本解法用长度为 n 的数组更直观。

参考代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // dp[i] 表示「踏上第 i 级台阶」的最小累计花费
        int[] dp = new int[n];
        dp[0] = cost[0];                 // 从 0 起步，踏上 0 就花 cost[0]
        dp[1] = cost[1];                 // 从 1 起步，踏上 1 就花 cost[1]
        for (int i = 2; i < n; i++) {
            // 踏上 i 要么从 i-1 来，要么从 i-2 来，取更便宜的，再付 cost[i]
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 楼顶在下标 n：从 n-1 跨一步，或从 n-2 跨两步，到顶不再收费
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}

同样可以滚动成 O(1) 空间：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = cost[0];   // dp[i-2]
        int prev1 = cost[1];   // dp[i-1]
        for (int i = 2; i < n; i++) {
            int cur = Math.min(prev1, prev2) + cost[i];
            prev2 = prev1;
            prev1 = cur;
        }
        return Math.min(prev1, prev2);
    }
}

复杂度：时间 O(n)，空间 O(1)（滚动版）。n ≤ 1000，毫无压力。

9.5打家劫舍（中等，力扣 198）

中等 核心：「偷或不偷」的决策式转移

题意：一排房子，第 i 间有 nums[i] 的钱。你不能同时偷相邻两间（会触发报警）。问最多能偷到多少钱。 例如 nums = [2,7,9,3,1]，最优是偷第 1、3、5 间（下标 0、2、4），共 2+9+1 = 12。

思路推导

暴力想法是枚举所有「不相邻」的组合，那是指数级的。我们用 DP 把「到某一间为止的最优」算出来。

状态：dp[i] = 考虑前 i 间房（下标 0..i），在满足不相邻约束下，最多能偷到的钱。

重点来了：站在第 i 间房门口，你只有两个选择——

• 不偷第 i 间：那 dp[i] 就等于「前 i-1 间的最优」，即 dp[i-1]。
• 偷第 i 间：那第 i-1 间不能偷，dp[i] = dp[i-2] + nums[i]。

取两者较大者，就是到 i 为止的最优：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

这就是典型的「决策型转移」——每一个状态都是「做 vs 不做」两种分支里取最优。 后面背包问题里你会反复见到这种二选一的结构。

初始化：dp[0] = nums[0]（只有一间，只能偷它）；dp[1] = max(nums[0], nums[1])（两间里挑钱多的）。 从 i=2 起用转移方程。

参考代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];          // 只有一间，直接偷
        // dp[i] 表示考虑前 i+1 间（下标 0..i）能偷到的最大金额
        int[] dp = new int[n];
        dp[0] = nums[0];                      // 第一间：只能偷
        dp[1] = Math.max(nums[0], nums[1]);   // 前两间：挑钱多的
        for (int i = 2; i < n; i++) {
            // 不偷第 i 间 -> dp[i-1]；偷第 i 间 -> dp[i-2] + nums[i]
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];                     // 考虑全部房间后的最优
    }
}

滚动数组版本（只用到前两项）：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int prev2 = nums[0];                       // 相当于 dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]);    // 相当于 dp[i-1]
        for (int i = 2; i < n; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

复杂度：时间 O(n)，空间 O(1)（滚动版）。n ≤ 100，轻松通过。

9.6不同路径（中等，力扣 62）

中等 核心：二维 DP 入门

题意：一个 m 行 n 列的网格，机器人从左上角 (0,0) 出发，每次只能向右或向下走，问走到右下角 (m-1, n-1) 共有多少条不同路径。 例如 m=3, n=7，答案是 28；m=2, n=3，答案是 3。

思路推导

一维 DP 你会了，这道题把它升成二维。状态自然变成两个下标：

dp[i][j] = 从起点走到格子 (i, j) 的路径数。

要到达 (i, j)，最后一步只有两种来源：

• 从上方 (i-1, j) 向下走一步；
• 从左方 (i, j-1) 向右走一步。

而且这两类路径互不重叠（最后一步方向不同），所以：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化：第一行所有格子只能一直向右走，所以 dp[0][j] = 1；第一列所有格子只能一直向下走，dp[i][0] = 1。 其余格子按转移方程从左往右、从上往下填。

参考代码

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示走到 (i,j) 的路径数
        int[][] dp = new int[m][n];
        // 初始化第一行、第一列：都只有 1 条路（一直右 / 一直下）
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        // 逐行逐列填表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

滚动数组优化（提一嘴）：dp[i][j] 只依赖「上一行同一列」和「本行左边」，所以可以用一维数组滚动——每一行从左到右更新时， dp[j] = dp[j]（上一行的旧值，相当于 dp[i-1][j]）+ dp[j-1]（本行已更新的左边）。注意等号右边的 dp[j] 此时还是上一行的：

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        // 第一行全是 1
        for (int j = 0; j < n; j++) dp[j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j] 左侧是上一轮值(=dp[i-1][j])，右侧 dp[j-1] 已是本行新值
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

复杂度：时间 O(m×n)，空间 O(n)（滚动版）或 O(m×n)（二维版）。m, n ≤ 100，都没问题。

9.7本专题常见坑

9.8自测题