动态规划：从状态定义到状态转移

我最开始接触“动态规划：从状态定义到状态转移”时，先遇到的是这个问题：我以前学动态规划总从公式开始背，结果公式记住了，换一个限制条件就不知道状态和选择发生了什么变化。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。

动态规划经常被认为是算法里最难的一块。难点不是代码长，而是状态定义不清楚时，公式看起来像凭空变出来。

我的理解是：动态规划就是把重复子问题保存下来，并按依赖关系逐步推出答案。它和递归、搜索非常近，只是更强调“状态”和“转移”。

它从哪里来

Richard Bellman 在二十世纪五十年代系统发展动态规划，用于多阶段决策与控制问题。“动态规划”不是因为代码里有数组，而是把大问题拆成会重复出现的状态，只求一次并保存结果。

DP 的核心问题

动态规划状态表

图：动态规划通过状态表复用已经计算过的子问题

写一篇 DP 题解，必须回答六个问题：

状态是什么？
选择是什么？
转移从哪里来？
base case 是什么？
遍历顺序为什么这样？
是否可以空间压缩？

如果这六个问题没回答，公式再漂亮也不稳。

从斐波那契理解重复子问题

递归写法：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这个写法会重复计算大量子问题。加缓存以后：

int fib(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return dfs(n, memo);
}

int dfs(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
    return memo[n];
}

这就是记忆化搜索。改成自底向上：

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

这就是动态规划表。

线性 DP：打家劫舍

问题：相邻房子不能同时偷，求最大金额。

状态定义：dp[i] 表示偷到第 i 间房子时，前 i 间能拿到的最大金额。

选择：

不偷第 i 间：dp[i - 1]
偷第 i 间：dp[i - 2] + nums[i]

int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[nums.length - 1];
}

空间可以压缩成两个变量，因为当前状态只依赖前两个状态。

背包 DP

0-1 背包是 DP 的经典模型：每个物品只能选一次，在容量限制下最大化价值。

int knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weight[i - 1]) {
                dp[i][w] = Math.max(dp[i][w],
                        dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

如果压缩成一维，容量必须倒序遍历，防止同一个物品被重复使用。

for (int i = 0; i < n; i++) {
    for (int w = capacity; w >= weight[i]; w--) {
        dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

完全背包则容量正序遍历，因为每个物品可以重复选择。

子序列 DP

最长公共子序列 LCS：

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

二维 DP 常见于两个字符串、两个序列、区间和棋盘路径。

DP 常见类型

类型	典型问题	核心
线性 DP	爬楼梯、打家劫舍、最大子数组	当前依赖前面若干状态
背包 DP	0-1、完全、多重背包	容量限制下做选择
子序列 DP	LIS、LCS、编辑距离	两个序列的状态关系
区间 DP	合并石子、回文区间	小区间推出大区间
树形 DP	树上最大路径、树上选择	子树状态合并
状压 DP	旅行商、集合选择	用位掩码表示集合

常见错误

只背公式，不知道状态含义。
base case 没初始化。
遍历顺序不满足依赖关系。
一维压缩方向写反。
状态维度缺失，导致信息不够。
把贪心问题硬写成 DP，复杂度变高。

工程场景

动态规划在工程中常见于：

编辑距离和文本相似度。
路径规划。
资源分配和预算优化。
推荐系统中的序列建模思维。
编译器、解析器和字符串处理。
任务调度和容量规划。

工程里的 DP 往往还要考虑状态数量是否可控。如果状态爆炸，必须重新建模、剪枝或近似。

面试题

动态规划和记忆化搜索是什么关系？
为什么 0-1 背包一维压缩要倒序遍历？
如何判断一个问题能不能用 DP？
状态定义为什么比转移公式更重要？
贪心和 DP 的区别是什么？

小结

DP 不是玄学。它的本质是状态定义、选择、转移和复用。只要把“这个状态代表什么”说清楚，再确认依赖顺序，很多题就会从背模板变成推逻辑。