LeetCode热门100

动态规划模块 — LeetCode 热门 100 题精讲（Java 向）

从斐波那契到背包，从线性DP到区间DP，十道经典题覆盖动态规划的核心模型，一网打尽

动态规划核心思想

动态规划（Dynamic Programming，DP）是解决多阶段决策问题的最优化方法。其核心是 将原问题分解为重叠子问题，通过 状态定义 和 状态转移方程，避免重复计算，将指数级复杂度降为多项式级。

DP 解题五步曲：

  1. 确定状态：分析问题中变化的维度，定义 dp 数组含义（如 dp[i] 表示前 i 个元素的最优解）。
  2. 状态转移：找出当前状态与之前状态的依赖关系，写出递推公式。
  3. 初始化：设置边界条件，确保递推正确开始。
  4. 遍历顺序：确保计算当前状态时所用到的前置状态已经计算完毕。
  5. 结果提取：从 dp 数组中获取最终答案（可能是 dp[n]，也可能是 max/min 值）。

LeetCode 热门 100 题中，DP 题占比较大，以下精选 10 道核心题，覆盖 线性DP、背包DP、区间DP、子序列DP 等多种模型，帮助你系统掌握。

1. 爬楼梯（LeetCode 70）

题目：每次可爬 1 或 2 级台阶，求到达第 n 级台阶的不同方法数。

状态定义：dp[i] 表示到达第 i 级台阶的方法数。

状态转移：dp[i] = dp[i-1] + dp[i-2]（要么从 i-1 跨 1 级，要么从 i-2 跨 2 级）。

初始化：dp[0]=1（表示不动），dp[1]=1。

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

复杂度：O(n) 时间，O(n) 空间（可优化为 O(1)）。

2. 杨辉三角（LeetCode 118）

题目：生成杨辉三角的前 numRows 行。

状态定义：dp[i][j] 表示第 i 行第 j 个元素（0 索引）。

状态转移：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]，两端为 1。

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) row.add(1);
            else row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
        }
        res.add(row);
    }
    return res;
}

复杂度：O(numRows²)，空间 O(numRows²)（输出本身）。

3. 打家劫舍（LeetCode 198）

题目：沿街房屋有非负金额，相邻房屋不能同时偷，求最大盗窃金额。

状态定义：dp[i] 表示前 i 间房屋（0~i-1）能偷到的最大金额。

状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])（偷第 i-1 间或不偷）。

初始化：dp[0]=0, dp[1]=nums[0]。

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

复杂度：O(n) 时间，O(1) 可优化。

4. 完全平方数（LeetCode 279）

题目：给定 n，求最少的完全平方数（1,4,9,…）之和等于 n。

状态定义：dp[i] 表示凑成 i 所需的最小平方数个数。

状态转移：dp[i] = min(dp[i - j*j] + 1) 对所有 j² ≤ i。

初始化：dp[0]=0，其余为 INF。

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
        }
    }
    return dp[n];
}

复杂度：O(n * √n)，空间 O(n)。

5. 零钱兑换（LeetCode 322）

题目：给定不同面额的硬币 coins 和总金额 amount，求凑成总金额所需的最少硬币数（可重复使用）。

状态定义：dp[i] 表示凑成金额 i 所需最少硬币数。

状态转移：dp[i] = min(dp[i - coin] + 1) 对所有 coin ∈ coins。

初始化：dp[0]=0，其余为 INF。

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 (i >= coin) dp[i] = Math.min(dp[i], dp[i-coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

复杂度：O(amount * coins.length)，空间 O(amount)。

6. 单词拆分（LeetCode 139）

题目：给定字符串 s 和字典 wordDict，判断 s 是否可拆分成字典中的单词。

状态定义：dp[i] 表示 s 的前 i 个字符（0~i-1）能否被拆分。

状态转移：dp[i] = true 当存在 j < i，使得 dp[j] = true 且 s[j:i] 在字典中。

初始化：dp[0]=true。

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && set.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

复杂度：O(n²) 时间，O(n) 空间。

7. 最长递增子序列（LeetCode 300）

题目：给定数组 nums，求最长严格递增子序列的长度。

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

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

初始化：dp[i]=1（至少包含自己）。

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int maxLen = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

复杂度：O(n²) 时间，O(n) 空间（可用二分优化到 O(n log n)）。

8. 乘积最大子数组（LeetCode 152）

题目：给定整数数组 nums，找出乘积最大的连续子数组（至少包含一个数）。

状态定义：维护两个状态，dpMax[i] 表示以 i 结尾的最大乘积，dpMin[i] 表示以 i 结尾的最小乘积（考虑负数）。

状态转移：

  • dpMax[i] = max(nums[i], nums[i]*dpMax[i-1], nums[i]*dpMin[i-1])
  • dpMin[i] = min(nums[i], nums[i]*dpMax[i-1], nums[i]*dpMin[i-1])
public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int tempMax = max, tempMin = min;
        max = Math.max(nums[i], Math.max(nums[i] * tempMax, nums[i] * tempMin));
        min = Math.min(nums[i], Math.min(nums[i] * tempMax, nums[i] * tempMin));
        res = Math.max(res, max);
    }
    return res;
}

复杂度：O(n) 时间，O(1) 空间。

9. 分割等和子集（LeetCode 416）

题目：给定非空数组 nums，判断是否可以分成两个和相等的子集。

状态定义：dp[j] 表示是否可以用 nums 中的某些数凑出总和 j。

状态转移：dp[j] = dp[j] || dp[j - num]（01 背包，每个数只能用一次）。

初始化：dp[0]=true。

public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

复杂度：O(n * sum/2)，空间 O(sum/2)。

10. 最长有效括号（LeetCode 32）

题目：给定仅包含 ‘(’ 和 ‘)’ 的字符串，求最长有效（格式正确且连续）括号子串的长度。

状态定义：dp[i] 表示以字符 i 结尾的最长有效括号子串长度。

状态转移：

  • 若 s[i] == ‘)’ 且 s[i-1] == ‘(’，则 dp[i] = (i>=2 ? dp[i-2] : 0) + 2
  • 若 s[i] == ‘)’ 且 s[i-1] == ‘)’，且 s[i - dp[i-1] - 1] == ‘(’，则 dp[i] = dp[i-1] + (i-dp[i-1]-2 >=0 ? dp[i-dp[i-1]-2] : 0) + 2
public int longestValidParentheses(String s) {
    int maxLen = 0;
    int[] dp = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i-1) == '(') {
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            } else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                dp[i] = dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
    return maxLen;
}

复杂度：O(n) 时间，O(n) 空间。

十题对比与分类

题目 DP类型 状态维度 核心转移 空间优化
70. 爬楼梯 线性DP 一维 dp[i] = dp[i-1]+dp[i-2] O(1)
118. 杨辉三角 二维DP 二维 dp[i][j] = dp[i-1][j-1]+dp[i-1][j] 按需
198. 打家劫舍 线性DP（选/不选） 一维 max(dp[i-1], dp[i-2]+nums[i]) O(1)
279. 完全平方数 完全背包 一维 min(dp[i - j²] + 1) 不可
322. 零钱兑换 完全背包 一维 min(dp[i-coin]+1) 不可
139. 单词拆分 线性DP + 集合 一维 dp[j] && set.contains(s[j:i]) 不可
300. 最长递增子序列 子序列DP 一维 max(dp[j]+1) if nums[j]<nums[i] 不可
152. 乘积最大子数组 双状态DP 一维+min max/min 三种情况 O(1)
416. 分割等和子集 01背包 一维布尔 dp[j] = dp[j]
32. 最长有效括号 区间DP/线性 一维 匹配前一个 ‘)’ 或 ‘(’ 不可

共同本质：所有 DP 题都通过 状态定义 和 转移方程 将原问题分解为子问题，并利用子问题的解构建原问题的解。

不同侧重：

  • 线性DP：70、198、139、300、32，状态转移简单，依赖前几个状态。
  • 背包DP：279、322、416，分完全背包和01背包，注意遍历顺序（正序/逆序）。
  • 多维状态：152 需要维护最大和最小两个状态，处理负数。
  • 二维输出：118 直接构造二维表。

总结：动态规划的核心心法

动态规划的本质是"记忆化搜索"，用空间换时间。核心在于找到正确的状态定义和转移方程，这通常需要分析"最后一步"或"子问题"的依赖关系。

DP 解题通用流程：

  1. 定义状态：明确 dp 数组每个位置的含义，最好用自然语言描述清楚。
  2. 转移方程：根据"最后一步"推导 dp[i] 与之前状态的关系。
  3. 初始化和边界：设置 dp[0] 或 dp 的初始值，确保递推正确。
  4. 遍历顺序：确保计算 dp[i] 时，所依赖的 dp[j] 已经计算完毕。
  5. 返回结果：根据题意，dp[n] 可能是答案，也可能需要遍历 dp 取最值。
© 2026 奇伏禾

🤖