经典算法专栏 #03：动态规划

动态规划（DP）是解决最优化问题的核心思想：将大问题分解为相互重叠的子问题，用备忘录避免重复计算。本文深度讲解 DP 三要素、五大类型，每类给出 2-3 道经典题的完整代码。

目录

DP 本质与三要素

动态规划是一种思想，而非具体算法：利用已计算好的结果推导新的计算，即大规模问题的结果由小规模问题的结果运算得来。

三要素

适合用 DP 的问题特征

1. 求最优解（最大值/最小值）：先考虑贪心，贪心不行再 DP
2. 求可行性（True/False）：如能否凑出某金额
3. 求方案总数：如路径数量

两个陷阱：数据可排序时用排序而非 DP；存在全排列时用回溯而非 DP（无重叠子问题）。

解题框架

五步法适用于所有 DP 问题。核心原则：遍历时，所依赖的子问题必须已经计算完毕；遍历终点必须是存储最终答案的位置。

线性 DP

线性 DP 的状态沿某个线性顺序（数组下标）推进，dp[i] 依赖前面若干个状态。

最长递增子序列（LIS）

问题：给定无序整数数组，找最长严格递增子序列的长度（子序列不要求连续）。

状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度。

为什么要以 nums[i] 结尾？ 因为只有固定了末尾元素，才能明确地判断"哪些前驱可以接在它前面"（nums[j] < nums[i]），从而写出确定性的转移方程。

状态转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]。

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);          // 每个元素自身就是长度 1 的子序列
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}
// 时间 O(n²)，空间 O(n)
// 进阶：用二分查找可优化到 O(nlogn)

O(nlogn) 优化（耐心排序/贪心 + 二分）：

public int lengthOfLIS_nlogn(int[] nums) {
    // tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
    // 为什么维护最小末尾？末尾越小，后续能接的元素越多，贪心最优
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int lo = 0, hi = size;
        while (lo < hi) {          // 二分找第一个 >= num 的位置
            int mid = (lo + hi) / 2;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = num;
        if (lo == size) size++;    // 扩展序列长度
    }
    return size;
}

编辑距离

问题：将 word1 转换为 word2 所需的最少操作数（插入/删除/替换各算 1 步）。

状态定义：dp[i][j] = word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数。

为什么用二维？ 两个字符串各有一个"进度"变量，必须同时追踪两者的位置，因此需要二维状态。

状态转移：

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]          // 字符相同，无需操作
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],    // 删除 word1[i-1]（等价于 word1 少一个字符去匹配）
        dp[i][j-1],    // 插入 word2[j-1]（等价于 word2 少一个字符去匹配）
        dp[i-1][j-1]   // 替换（两者各少一个字符）
    )

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 初始化：空字符串的转换代价
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                               Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}
// 时间 O(mn)，空间 O(mn)，可优化到 O(min(m,n))

打家劫舍

问题：一排房子，不能抢相邻两间，求最大金额。

状态定义：dp[i] = 抢前 i 间房子的最大金额。

状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

直觉：对第 i 间房，只有两种选择——不抢（继承 dp[i-1]）或抢（dp[i-2] + 当前价值）。

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    // 空间优化：只需保留前两个状态
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
// 时间 O(n)，空间 O(1)

区间 DP

区间 DP 的状态定义在某个区间 [i, j] 上，通过枚举分割点，由更小区间的解推导更大区间的解。

计算方向：必须按区间长度从小到大，因为大区间依赖小区间的结果。

最长回文子序列

问题：给定字符串，找最长回文子序列的长度（子序列不要求连续）。

状态定义：dp[i][j] = 字符串 s[i..j] 中最长回文子序列的长度。

状态转移：

if s[i] == s[j]:
    dp[i][j] = 2 + dp[i+1][j-1]   // 两端字符可以配对，内部子问题贡献加2
else:
    dp[i][j] = max(dp[i+1][j], dp[i][j-1])  // 去掉左端或右端，取较大值

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1; // 单个字符是长度 1 的回文

    // 按区间长度从小到大枚举（计算方向：从右下往左上，保证 dp[i+1][j-1] 已计算）
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = 2 + dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}
// 时间 O(n²)，空间 O(n²)

戳气球

问题：n 个气球排成一排，每个有数字 nums[i]。戳破气球 i 得到 nums[i-1]*nums[i]*nums[i+1] 金币，求戳破所有气球的最大金币数。

关键技巧：反向思维——不考虑"先戳哪个"，而是考虑"最后戳哪个"。

为什么反向？ 正向思维中，戳破一个气球后相邻关系会变化，子问题之间有依赖，无法独立求解。反向思维固定最后一个被戳的气球 k，此时 (i,k) 和 (k,j) 两个子问题完全独立。

状态定义：dp[i][j] = 戳破开区间 (i, j) 内所有气球的最大金币（两端是虚拟边界）。

状态转移：枚举最后一个被戳破的气球 k：

dp[i][j] = max over k in (i+1, j-1) of:
    dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]

public int maxCoins(int[] nums) {
    int n = nums.length;
    // 添加虚拟边界 1
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
    int m = n + 2;

    int[][] dp = new int[m][m];
    // 区间长度从 2 开始（至少包含一个真实气球）
    for (int len = 2; len < m; len++) {
        for (int i = 0; i + len < m; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]);
            }
        }
    }
    return dp[0][m - 1];
}
// 时间 O(n³)，空间 O(n²)

背包 DP

背包问题是 DP 的经典模型，核心在于"选或不选"的决策。一维空间优化是面试重点。

0-1 背包 vs 完全背包：遍历方向的本质区别

0-1 背包

问题：n 件物品，重量 w[i]、价值 v[i]，背包容量 W，每件只能选一次，求最大价值。

状态定义：dp[j] = 容量为 j 时的最大价值（一维优化版）。

public int knapsack01(int[] w, int[] v, int n, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {    // 从后往前！防止同一物品被选多次
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}
// 时间 O(nW)，空间 O(W)

二维原始版（便于理解）：

// dp[i][j] = 前 i 件物品、容量 j 时的最大价值
// dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])  if j >= w[i]
// dp[i][j] = dp[i-1][j]                                 if j < w[i]

完全背包

问题：每件物品可选无限次，求最大价值。

public int knapsackComplete(int[] w, int[] v, int n, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int j = w[i]; j <= W; j++) {    // 从前往后！允许重复选同一物品
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}
// 时间 O(nW)，空间 O(W)

经典应用：零钱兑换（完全背包变体）

// 给定硬币面值数组，凑出 amount 的最少硬币数
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);    // 初始化为不可达（任何合法值都小于 amount+1）
    dp[0] = 0;
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

分组背包

问题：物品分成若干组，每组最多选一件，求最大价值。

关键：枚举组内物品时，容量必须从后往前（同 0-1 背包），保证每组只选一件。

public int knapsackGroup(int[][] groups, int[] groupSize, int W) {
    // groups[i][j] = 第 i 组第 j 件物品的 [weight, value]
    int[] dp = new int[W + 1];
    for (int i = 0; i < groups.length; i++) {
        for (int j = W; j >= 0; j--) {          // 外层容量从后往前
            for (int k = 0; k < groupSize[i]; k++) { // 枚举组内物品
                int wi = groups[i][k * 2];
                int vi = groups[i][k * 2 + 1];
                if (j >= wi) {
                    dp[j] = Math.max(dp[j], dp[j - wi] + vi);
                }
            }
        }
    }
    return dp[W];
}

树形 DP

树形 DP 在树结构上进行动态规划，通常通过 DFS 后序遍历，从叶节点向根节点汇聚状态。

为什么用后序遍历？ 父节点的状态依赖子节点的状态，必须先算完所有子节点再处理父节点。

树的最大独立集

问题：给定一棵树，选出一些节点使得没有两个相邻节点都被选中，且所选节点权值之和最大。

状态定义：

• dp[u][1] = 以 u 为根的子树中，选择节点 u 时的最大权值
• dp[u][0] = 以 u 为根的子树中，不选择节点 u 时的最大权值

int[][] dp;
int[] val;
List<List<Integer>> children;

void dfs(int u) {
    dp[u][1] = val[u];    // 选 u，初始值为 u 的权值
    dp[u][0] = 0;         // 不选 u
    for (int v : children.get(u)) {
        dfs(v);
        dp[u][1] += dp[v][0];                        // 选 u，则子节点不能选
        dp[u][0] += Math.max(dp[v][0], dp[v][1]);    // 不选 u，子节点任意
    }
}

public int maxIndependentSet(int root) {
    dfs(root);
    return Math.max(dp[root][0], dp[root][1]);
}

树形背包（选课问题）

问题：树形结构的课程，选某门课前必须先选其前置课程，每门课有学分，在选 m 门课的约束下求最大学分。

思路：将树形背包转化为分组背包，每个节点的子树视为一组，DFS 时合并背包。

// dp[u][j] = 以 u 为根的子树中，选 j 门课的最大学分
// 合并子树时：枚举分配给当前子树的课程数 k
void dfs(int u, int m) {
    dp[u][1] = score[u];   // 至少选 u 本身
    for (int v : children.get(u)) {
        dfs(v, m);
        // 逆序合并，防止重复
        for (int j = m; j >= 1; j--) {
            for (int k = 0; k < j; k++) {
                dp[u][j] = Math.max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

状态压缩 DP

当状态可以用一个整数的二进制位表示时，使用状态压缩 DP。典型场景：集合中元素的"选/未选"状态，n 通常 ≤ 20。

为什么用位运算？ n 个元素的选择状态有 2ⁿ 种，用一个整数的二进制位表示，空间紧凑且操作高效。

旅行商问题（TSP）

问题：从城市 0 出发，经过所有城市恰好一次后回到 0，求最短路径。

状态定义：dp[mask][i] = 已访问城市集合为 mask、当前在城市 i 时的最短路径。

public int tsp(int[][] dist) {
    int n = dist.length;
    int full = 1 << n;
    int[][] dp = new int[full][n];
    // 初始化为无穷大
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0;    // 从城市 0 出发，初始只访问了城市 0（mask = 0001）

    for (int mask = 1; mask < full; mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;  // i 不在当前路径中
            if (dp[mask][i] == Integer.MAX_VALUE / 2) continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) continue;  // j 已访问
                int newMask = mask | (1 << j);
                dp[newMask][j] = Math.min(dp[newMask][j], dp[mask][i] + dist[i][j]);
            }
        }
    }
    // 回到城市 0
    int ans = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) {
        ans = Math.min(ans, dp[full - 1][i] + dist[i][0]);
    }
    return ans;
}
// 时间 O(2^n * n²)，空间 O(2^n * n)

棋盘覆盖问题（骨牌铺满）

问题：用 1×2 的骨牌铺满 m×n 的棋盘，求方案数。

思路：逐列处理，用 mask 表示当前列向下一列"突出"的格子状态，通过 DFS 枚举合法的骨牌放置。

// 经典状压 DP：m 行 n 列棋盘铺满 1x2 骨牌的方案数
// dp[j][mask] = 处理到第 j 列，当前列向右突出的状态为 mask 时的方案数
public long dominoTiling(int m, int n) {
    long[] dp = new long[1 << m];
    dp[0] = 1;
    for (int col = 0; col < n; col++) {
        long[] newDp = new long[1 << m];
        // 枚举上一列的突出状态 prevMask 和当前列的竖向骨牌状态 curMask
        for (int prevMask = 0; prevMask < (1 << m); prevMask++) {
            if (dp[prevMask] == 0) continue;
            dfsPlace(0, m, prevMask, 0, dp[prevMask], newDp);
        }
        dp = newDp;
    }
    return dp[0];
}

void dfsPlace(int row, int m, int prevMask, int curMask,
              long ways, long[] newDp) {
    if (row == m) {
        newDp[curMask] += ways;
        return;
    }
    // 当前行被上一列突出的骨牌占据，只能放竖骨牌（向右突出）
    if ((prevMask >> row & 1) == 1) {
        dfsPlace(row + 1, m, prevMask, curMask | (1 << row), ways, newDp);
    } else {
        // 放横骨牌（当前列不突出）
        dfsPlace(row + 1, m, prevMask, curMask, ways, newDp);
        // 放竖骨牌（当前列向右突出），需要下一行也未被占
        if (row + 1 < m && (prevMask >> (row + 1) & 1) == 0) {
            dfsPlace(row + 2, m, prevMask, curMask | (1 << row) | (1 << (row + 1)),
                     ways, newDp);
        }
    }
}

经典加餐

买卖股票系列

买卖股票是 DP 中的经典系列，核心是用三维状态 dp[i][j][k] 建模：

• i：第 i 天
• j：是否持股（0=未持股，1=持股）
• k：已卖出次数

最多两次交易（LeetCode 123）：

public int maxProfit(int[] prices) {
    int m = prices.length;
    // dp[i][j][k]: 第i天，j=是否持股，k=已卖出次数(0/1/2)
    int[][][] dp = new int[m][2][3];
    dp[0][0][0] = 0;
    dp[0][1][0] = -prices[0];
    dp[0][1][1] = -prices[0];
    dp[0][1][2] = Integer.MIN_VALUE / 2;  // 不可能的状态

    for (int i = 1; i < m; i++) {
        dp[i][0][0] = 0;
        dp[i][0][1] = Math.max(dp[i-1][1][0] + prices[i], dp[i-1][0][1]);
        dp[i][0][2] = Math.max(dp[i-1][1][1] + prices[i], dp[i-1][0][2]);
        dp[i][1][0] = Math.max(dp[i-1][0][0] - prices[i], dp[i-1][1][0]);
        dp[i][1][1] = Math.max(dp[i-1][0][1] - prices[i], dp[i-1][1][1]);
        dp[i][1][2] = Integer.MIN_VALUE / 2;
    }
    return Math.max(dp[m-1][0][1], dp[m-1][0][2]);
}

通用模板（最多 k 次交易 + 冻结期 t + 手续费 c）：

dp[i][0][k] = max(dp[i-1][1][k-1] + prices[i],  dp[i-1][0][k])
dp[i][1][k] = max(dp[i-1-t][0][k] - prices[i] - c, dp[i-1][1][k])

DP 解题 Checklist

在写 DP 代码前，先确认：

• [ ] 问题满足三要素（最优子结构、无后效性、重叠子问题）
• [ ] 状态定义清晰（dp[i] 或 dp[i][j] 表示什么）
• [ ] 初始化状态正确（边界条件）
• [ ] 状态转移方程写出来了
• [ ] 计算方向正确（依赖的子问题已提前计算）
• [ ] 考虑空间优化（滚动数组或一维压缩）

参考资料

• 极客时间《动态规划面试宝典》— 卢誉声
• 《算法导论》— 第 15 章动态规划
• LeetCode 专题：动态规划