力扣 Hot100 动态规划刷题心法：从入门到精通的蜕变之路

 在无数个与动态规划博弈的深夜后，我终于参透了状态转移的奥义。动态规划作为算法领域的 "硬骨头"，曾让我在力扣刷题之路上屡屡碰壁。但经过数百次提交与反思，我逐渐找到了突破 DP 瓶颈的方法论。本文将结合力扣 Hot100 经典题目，分享从 DP 小白到独立解题的蜕变之路。

一、刷题心路：从迷茫到顿悟的旅程

初次接触力扣 Hot100 时，动态规划就像一座难以逾越的高山。记得第一次做【70. 爬楼梯】时，我盯着题目发呆半小时，直到看到题解中那句 "当前状态 = 前两阶状态之和" 才恍然大悟。DP 的核心在于状态定义与状态转移，这需要突破常规思维模式：

1. 三阶段成长轨迹

• 阶段 1：看题就懵（如【322. 零钱兑换】）
  面对 "给定不同面额的硬币，计算凑成总金额所需的最少硬币数"，完全无法将问题拆解为子问题

• 阶段 2：看懂题解但写不出（如【139. 单词拆分】）
  理解了 "dp [i] 表示 s [0..i-1] 是否可被拆分" 的状态定义，却无法独立推导出状态转移的逻辑

• 阶段 3：能独立推导状态方程（如【198. 打家劫舍】）
  开始掌握 "选与不选" 的决策思维，能自主分析子问题间的依赖关系

2. 关键顿悟时刻

• 发现背包问题本质是选择与放弃的艺术：每个物品的决策都会影响后续状态
• 理解字符串 DP 中【编辑距离】的二维状态设计：dp [i][j] 表示将字符串 A 前 i 个字符转为 B 前 j 个字符的最小操作数
• 掌握树形 DP 中【124. 二叉树最大路径和】的后序遍历逻辑：每个节点的状态需要基于左右子树的计算结果

二、动态规划核心框架（五步法）

动态规划的解题过程可以抽象为统一的五步法框架，这是突破各类 DP 题的通用钥匙：

public int dpSolution(int[] nums) {
    // 1. 状态定义：dp[i]代表什么状态？
    int n = nums.length;
    int[] dp = new int[n];
    
    // 2. 边界初始化：处理最小规模的子问题
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    // 3. 状态转移方程（核心）：如何从子问题推导当前问题
    for (int i = 2; i < n; i++) {
        // 关键决策点：选or不选？
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    // 4. 遍历顺序：确保计算当前状态时依赖的状态已计算完成
    // （此处为从左到右的线性遍历）
    
    // 5. 返回目标状态：通常是dp数组的某个特定位置
    return dp[n-1];
}

三、Hot100 经典 DP 题目精析

1. 【70. 爬楼梯】 - 入门必做

这是 DP 最经典的入门题，核心在于发现斐波那契数列的递推关系：

public int climbStairs(int n) {
    if (n <= 2) return n;
    
    // 状态压缩优化：只需要保存前两个状态
    int prev = 1;  // 前一阶的方法数
    int curr = 2;  // 当前阶的方法数
    
    for (int i = 3; i <= n; i++) {
        int next = prev + curr;  // 下一阶的方法数
        prev = curr;
        curr = next;
    }
    
    return curr;
}

核心思想：当前阶的方法数 = 前一阶的方法数 + 前两阶的方法数

2. 【198. 打家劫舍】 - 决策思维训练

这是 "选与不选" 决策模型的典型应用：

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    
    // dp[i]表示前i个房子能偷到的最大金额
    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++) {
        // 决策点：偷当前房子(i)则不能偷前一个(i-1)
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp[nums.length - 1];
}

状态压缩优化：

public int rob(int[] nums) {
    int prevMax = 0;  // 不偷当前房子时的最大金额
    int currMax = 0;  // 偷当前房子时的最大金额
    
    for (int num : nums) {
        int temp = currMax;
        currMax = prevMax + num;  // 偷当前房子，前一个不能偷
        prevMax = Math.max(prevMax, temp);  // 不偷当前房子，取前两种情况的最大值
    }
    
    return Math.max(prevMax, currMax);
}

决策要点：相邻房子不能同时偷 → 对于每个房子，选择 "偷" 或 "不偷" 中的收益较大者

3. 【139. 单词拆分】 - 字符串 DP

这是字符串类 DP 的典型代表，需要逆向思考：

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    // dp[i]表示s的前i个字符能否被字典中的单词拆分
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;  // 空字符串可以被拆分
    
    // 将字典转换为集合，加速查找
    Set<String> dict = new HashSet<>(wordDict);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // 如果前j个字符能被拆分，且子串s[j,i)在字典中
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;  // 只要有一种拆分方式即可
            }
        }
    }
    
    return dp[n];
}

技巧：

• 外层循环遍历字符串长度
• 内层循环尝试不同的分割点
• 利用 HashSet 加速字典查找

4. 【322. 零钱兑换】 - 完全背包问题

这是典型的完全背包问题（每种物品可选无限次）：

public int coinChange(int[] coins, int amount) {
    // dp[i]表示凑成金额i所需的最少硬币数
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为一个不可能的值
    dp[0] = 0;  // 凑成金额0不需要任何硬币
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            // 状态转移：使用当前硬币或不使用
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];  // 如果无法凑成，返回-1
}

关键点：

• 外层遍历物品（硬币）
• 内层正序遍历容量（金额），体现每种硬币可重复使用
• dp [i] = min (dp [i], dp [i-coin] + 1) 表示使用当前硬币后的最优解

5. 【53. 最大子数组和】 - 子数组问题

这是子数组类 DP 的经典题目：

public int maxSubArray(int[] nums) {
    int n = nums.length;
    // dp[i]表示以nums[i]结尾的最大子数组和
    int[] dp = new int[n];
    dp[0] = nums[0];
    int maxSum = dp[0];
    
    for (int i = 1; i < n; i++) {
        // 决策：是加入前面的子数组，还是重新开始一个子数组
        dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
        maxSum = Math.max(maxSum, dp[i]);  // 更新全局最大值
    }
    
    return maxSum;
}

状态压缩优化：

public int maxSubArray(int[] nums) {
    int currMax = nums[0];  // 当前位置的最大子数组和
    int globalMax = nums[0];  // 全局最大子数组和
    
    for (int i = 1; i < nums.length; i++) {
        currMax = Math.max(nums[i], currMax + nums[i]);
        globalMax = Math.max(globalMax, currMax);
    }
    
    return globalMax;
}

决策要点：对于每个元素，决定是将其加入前面的子数组，还是以它为起点创建新的子数组

四、突破 DP 瓶颈的实战技巧

1. 降维打击法

很多二维 DP 问题可以优化为一维或常数空间：

• 滚动数组：将二维 DP 优化为一维（如【1143. 最长公共子序列】）
• 状态压缩：用位运算代替数组（如【464. 我能赢吗】）

以【62. 不同路径】为例，二维 DP 解法：

public int uniquePaths(int m, int n) {
    // dp[i][j]表示从起点到(i,j)的路径数
    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];
}

一维优化解法：

public int uniquePaths(int m, int n) {
    // 只需要保存一行的状态
    int[] dp = new int[n];
    
    // 初始化
    Arrays.fill(dp, 1);
    
    // 状态转移
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j-1];  // 等价于dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    
    return dp[n-1];
}

2. 树形 DP 模板

树形 DP 通常采用后序遍历，先处理子树，再处理根节点：

// 以【337.打家劫舍III】为例
public int rob(TreeNode root) {
    int[] result = robSub(root);
    return Math.max(result[0], result[1]);
}

// 返回一个长度为2的数组：[不偷当前节点的最大值, 偷当前节点的最大值]
private int[] robSub(TreeNode node) {
    if (node == null) return new int[2];
    
    // 后序遍历，先处理左右子树
    int[] left = robSub(node.left);
    int[] right = robSub(node.right);
    
    int[] result = new int[2];
    
    // 不偷当前节点，左右子树可偷可不偷，取最大值相加
    result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    
    // 偷当前节点，左右子树都不能偷
    result[1] = node.val + left[0] + right[0];
    
    return result;
}

3. Debug 锦囊

• 打印 DP 表：可视化状态转移过程，帮助理解问题
• 特殊用例验证：对空数组、单元素、全负数等边界情况进行手动推导
• 数学归纳法验证：确保状态转移方程在所有情况下都成立

五、高效刷题路线图

1. 新手村（1-2 周）

• 70. 爬楼梯 → 509. 斐波那契数（基础递推）
• 198. 打家劫舍 → 213. 打家劫舍 II（环形数组变体）
• 53. 最大子数组和 → 152. 乘积最大子数组（子数组问题进阶）

2. 进阶训练（2-3 周）

• 322. 零钱兑换 → 518. 零钱兑换 II（完全背包问题）
• 300. 最长递增子序列 → 673. 最长递增子序列的个数（子序列问题）
• 1143. 最长公共子序列 → 72. 编辑距离（字符串 DP）

3. 高手挑战（3-4 周）

• 124. 二叉树最大路径和（树形 DP）
• 312. 戳气球（区间 DP）
• 416. 分割等和子集（01 背包变体）
• 887. 鸡蛋掉落（决策优化）

六、致未来的自己

当你在深夜为状态转移方程抓狂时，请记住：每个 AC 的背后都有无数个 WA 的铺垫。我的刷题记录：

• 累计提交：427 次
• 首次独立解出 hard 题：编辑距离（耗时 3.5 小时）
• 最大收获：DP 思维迁移到实际开发需求分析中

刷题最大的惊喜不是通过率 100%，而是某天突然发现：曾经望而生畏的题目，现在能优雅地写出dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]这样的状态转移。这大概就是算法之美吧！

附录：DP 问题分类速查表