【橡皮绳的极限】动态规划入门：从记忆化到状态转移

橡皮绳拉到极限后弹回来，每次弹回的力量都基于前一次拉伸的状态——动态规划正是这样：每个子问题的最优解建立在更小子问题的最优解之上，层层叠加，最终弹射到全局最优。

动态规划的本质是「有记忆的暴力」。把 Gear 2 看作「加速枚举」，那 DP 就是「带缓存的枚举」，避免重复计算相同子问题。

一、从递归到 DP 的三步进化

以爬楼梯（LeetCode 70）为例——每次可以爬 1 或 2 级，到达 n 级共有多少种方法？

第一步：暴力递归

int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}
// 时间 O(2ⁿ)，大量重复计算

第二步：记忆化递归（Top-Down）

int climbStairs(int n) {
    return helper(n, new int[n + 1]);
}

int helper(int n, int[] memo) {
    if (n <= 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
}
// 时间 O(n)，空间 O(n)

第三步：迭代 DP（Bottom-Up）

int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}
// 时间 O(n)，空间 O(n)，还可压缩到 O(1)

空间压缩：因为 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，只需保留两个变量：

int a = 1, b = 2;
for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;

二、DP 四步法

定义 dp 数组：dp[i] 表示什么？
找状态转移方程：dp[i] 如何由前面的状态推导？
确定初始值（base case）
确定遍历顺序：从小到大还是从大到小？

三、一维 DP 经典题

打家劫舍（LeetCode 198）

相邻房屋不能同时抢，最大抢劫金额：

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

dp[i] = 前 i+1 间房屋能抢的最大金额。对于第 i 间房：

不抢：dp[i-1]
抢：dp[i-2] + nums[i]

零钱兑换（LeetCode 322）

用面值在 coins 中的硬币凑出 amount，最少需要几枚：

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为不可能的大值
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

dp[i] = 凑出金额 i 的最少硬币数。每枚硬币都试一次，取最小值。

最长递增子序列（LeetCode 300）

public int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 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;
}

dp[i] = 以 nums[i] 结尾的最长递增子序列长度。遍历 i 之前所有小于 nums[i] 的位置 j，取 dp[j] + 1 最大值。

O(n²) 解法，可以用 patience sorting 优化到 O(n log n)，详见进阶篇。

四、二维 DP 经典题

不同路径（LeetCode 62）

m×n 网格从左上走到右下，只能向右或向下，共有多少路径：

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;  // 第一列只能一路向下
    for (int j = 0; j < n; j++) dp[0][j] = 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];
}

最长公共子序列（LeetCode 1143）

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i-1) == text2.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[i][j] = text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度。字符相同时从左上角转移来（同时消耗两个字符）；不同时取上方或左方的最大值。

编辑距离（LeetCode 72）

将 word1 转换为 word2 的最少操作数（插入、删除、替换）：

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;  // 删除 i 次
    for (int j = 0; j <= n; j++) dp[0][j] = 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], // 删除 word1[i]
                        dp[i][j-1]  // 插入（相当于删除 word2[j]）
                    )
                );
        }
    }
    return dp[m][n];
}

五、DP vs 回溯的选择

特征	用 DP	用回溯
只需最优解（最大/最小/总数）	✓	—
需要枚举所有具体方案	—	✓
子问题有重叠	✓	—
需要路径还原	需额外记录 parent	天然记录路径
有后效性（当前决策影响未来约束）	—	✓

六、常见 DP 问题分类

线性 DP：爬楼梯、打家劫舍、LIS、LCS、编辑距离
区间 DP：戳气球、矩阵链乘法、石子归并
背包 DP：0/1 背包、完全背包（零钱兑换）、多重背包
树形 DP：打家劫舍 III、二叉树最大路径和
状态压缩 DP：旅行商问题、棋盘覆盖

橡皮绳拉到极限后反弹，弹力的大小取决于它被拉到哪一步——DP 的每一个 dp[i] 就是那个「极限记录」，等到更大的问题需要它时，直接拿来用，不需要重新拉伸一遍。

下一站：风车村 · 【果实的馈赠】排序算法全景——为什么你只需要记住 3 种