Go back

LeetCode Hot 100——动态规划篇（状态定义、转移方程、背包）

LeetCode Hot 100 · 动态规划篇

动态规划是面试中区分「背题党」和「真会党」的第一道分水岭。面试官看一个人写 DP，只看四件事：状态怎么定义、转移方程怎么列、初始化对不对、遍历顺序有没有错。本篇文章把 Hot 100 里的 9 道动态规划题全部拆成这套框架，每题都从暴力写法一路推到最优解，并给出复杂度逐步推导过程和 CodeTop 真实变体。

先记住这套「DP 四步走」：

  1. 状态定义：dp[i] / dp[i][j] 到底表示什么？这句话一定要能一字不差说出来。
  2. 转移方程：当前状态由哪些更小的子问题推出来？
  3. 初始化：dp[0] 是多少？边界下标会不会越界？
  4. 遍历顺序：正序还是倒序？这决定了背包问题里物品能不能重复用。

下面逐题手撕。

#70 爬楼梯

题意

爬 n 级楼梯，每次可以爬 1 级或 2 级，返回到达楼顶的不同方法数。

输入：n = 3   输出：3 （1+1+1, 1+2, 2+1）

难点与易错点

解法一：暴力 / 直观

直接递归，把「爬 n 级」分解成「爬 n-1 级」+「爬 n-2 级」两个子问题。

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

复杂度：每次调用分裂成两个子问题，形成一棵高度为 n 的二叉树，节点总数约 2^n，所以时间 O(2^n)，递归栈深度 O(n)。

瓶颈：大量重复计算——climbStairs(n-2) 会被 climbStairs(n-1) 和 climbStairs(n-3) 反复调用，指数级冗余。

解法二：优化 / 最优

状态定义：dp[i] = 爬到第 i 级的方法数。

转移方程：dp[i] = dp[i-1] + dp[i-2]（最后一步跨 1 级来自 i-1，跨 2 级来自 i-2）。

初始化：dp[0] = 1（空走法）、dp[1] = 1。实际用滚动变量：prev2 = 1（到达第 1 级）、prev1 = 2（到达第 2 级）。

遍历顺序：i 从 3 到 n 正序，滚动更新。

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int prev2 = 1, prev1 = 2; // 到达第 1、2 级的方法数

        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2; // dp[i] = dp[i-1] + dp[i-2]
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
}

复杂度逐步推导：循环变量 i 从 3 走到 n，共执行 n-2 次，每次 O(1)，所以时间 O(n-2) = O(n)。滚动变量只用 prev2、prev1 两个额外 int，不随 n 增长，空间 O(1)。

多解法对比

解法时间空间适用场景
暴力递归O(2^n)O(n)仅用于讲清子问题结构
记忆化递归O(n)O(n)想用递归但避免重复计算
滚动 DPO(n)O(1)面试首选，无额外空间

这题约束下，滚动 DP 时间 O(n) 已经是最优（至少要看一遍输入规模），空间 O(1) 也无法更省，所以选滚动 DP。

CodeTop 变体

#198 打家劫舍

题意

数组 nums 代表每间房的金额，相邻的房屋不能同时被打劫，返回能偷窃到的最大金额。

输入：nums = [2,7,9,3,1]   输出：12 （2+9+1）

难点与易错点

解法一：暴力 / 直观

每个房子两种选择（偷 / 不偷），递归枚举。

class Solution {
    public int rob(int[] nums) {
        return dfs(nums, nums.length - 1);
    }
    private int dfs(int[] nums, int i) {
        if (i < 0) return 0;
        // 不偷 i（看 i-1），或偷 i（跳过 i-1，看 i-2）
        return Math.max(dfs(nums, i - 1), dfs(nums, i - 2) + nums[i]);
    }
}

复杂度：每个状态分裂成两个子问题，树高 n，时间 O(2^n)，栈空间 O(n)。

瓶颈：dfs(i-2) 被 dfs(i-1) 和 dfs(i-3) 重复调用，指数级冗余，和爬楼梯同病。

解法二：优化 / 最优

状态定义：dp[i] = 打劫前 i+1 间房（下标 0..i）能拿到的最大金额。

转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

初始化：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。滚动变量 prev2 = nums[0]、prev1 = max(nums[0], nums[1])。

遍历顺序：i 从 2 到 n-1 正序，滚动更新。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];

        int prev2 = nums[0];                      // dp[0]
        int prev1 = Math.max(nums[0], nums[1]);   // dp[1]

        for (int i = 2; i < n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]); // 不偷 i vs 偷 i
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
}

复杂度逐步推导：循环 i 从 2 到 n-1 共 n-2 次，每次 O(1)，时间 O(n)。只有 prev2、prev1 两个变量，空间 O(1)。

多解法对比

解法时间空间适用场景
暴力递归O(2^n)O(n)讲清「偷/不偷」决策树
记忆化递归O(n)O(n)保留递归结构
滚动 DPO(n)O(1)面试首选

时间 O(n) 是下界（每个房子至少看一次），空间 O(1) 最优，故选滚动 DP。

CodeTop 变体

#279 完全平方数

题意

给你整数 n，返回和为 n 的完全平方数（1, 4, 9, 16…）的最少数量。

输入：n = 12   输出：3 （4+4+4）

难点与易错点

解法一：暴力 / 直观

DFS 回溯：每次枚举一个平方数减去，递归找最小个数。

class Solution {
    public int numSquares(int n) {
        if (n == 0) return 0;
        int res = Integer.MAX_VALUE;
        for (int j = 1; j * j <= n; j++) {
            res = Math.min(res, 1 + numSquares(n - j * j));
        }
        return res;
    }
}

复杂度：每个状态分支最多 √n 个，递归深度最坏 n（全是 1 的情况），时间指数级 O(n^(n/2)) 量级，栈空间 O(n)。

瓶颈：同一剩余值 n - j*j 被反复递归计算，存在大量重叠子问题。

解法二：优化 / 最优

状态定义：dp[i] = 凑出整数 i 所需的最少完全平方数个数。

转移方程：dp[i] = min(dp[i], dp[i - j*j] + 1)，对每个满足 j*j <= i 的 j 取最小。

初始化：dp[0] = 0，dp[1..n] = Integer.MAX_VALUE（表示「尚未找到」）。

遍历顺序：外层 i 从 1 到 n 正序，内层 j 枚举平方数（正序即可，因为这是「凑金额」型完全背包，i 从小到大天然保证 dp[i - j*j] 已算出）。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 凑出 0 需要 0 个完全平方数

        for (int i = 1; i <= n; i++) {
            for (int j = 1; (long) j * j <= i; j++) {
                if (dp[i - j * j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
        }

        return dp[n];
    }
}

复杂度逐步推导：外层 i 从 1 到 n 共 n 次；内层 j 从 1 到 √i，共 √i 次。总操作数 Σ(i=1..n) √i，这个和约为 (2/3)·n·√n（把离散和近似成 ∫√x dx），所以时间 O(n√n)。dp 数组长度 n+1，空间 O(n)。

多解法对比

解法时间空间适用场景
DFS 回溯指数级O(n)讲清「每次减一个平方数」的搜索树
完全背包 DPO(n√n)O(n)常规最优解
四平方和定理O(√n)O(1)面试加分项，数学技巧

这题约束 n 可达 10^4，O(n√n) ≈ 10^6 可以接受；四平方和定理是拉格朗日定理的产物（任意正整数可表示为至多 4 个平方数之和），可以作为「如果面试官要求更快」的补充回答。

CodeTop 变体

#322 零钱兑换

题意

给定一组硬币面值 coins 和总金额 amount，返回凑出 amount 所需的最少硬币数，无法凑出返回 -1（每种面值可重复使用）。

输入：coins = [1,5,11], amount = 15   输出：3 （5+5+5）

难点与易错点

解法一：暴力 / 直观

DFS 递归：每次选一个面值减去，求最小硬币数。

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (coin <= amount) {
                int sub = coinChange(coins, amount - coin);
                if (sub != -1) res = Math.min(res, sub + 1);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

复杂度：每个状态分支最多 coins.length 个，递归深度最坏 amount（全是面值 1），时间约 O(amount^coins.length)，栈空间 O(amount)。

瓶颈：同一剩余金额被反复计算，重叠子问题严重。

解法二：优化 / 最优

状态定义：dp[i] = 凑出金额 i 所需的最少硬币数。

转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)，对每个 coin <= i 的面值取最小。

初始化：dp[0] = 0，dp[1..amount] = amount + 1（充当「无穷大」）。

遍历顺序：外层 i 从 1 到 amount 正序，内层遍历每个 coin（正序 = 硬币可无限用）。

class Solution {
    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];
    }
}

复杂度逐步推导：外层 i 从 1 到 amount 共 amount 次；内层遍历 coins 共 coins.length 次。两层相乘，时间 O(amount × coins.length)。dp 数组长度 amount + 1，空间 O(amount)。

多解法对比

解法时间空间适用场景
贪心不一定正确O(1)仅币值有整除关系时可用
DFS 回溯指数级O(amount)讲清搜索树
完全背包 DPO(amount × len)O(amount)面试首选，唯一保证正确

这题约束下贪心会错（反例见难点），DFS 指数级不可行，只有 DP 既能保证正确性又是多项式时间，所以必须选 DP。

CodeTop 变体

#139 单词拆分

题意

给定字符串 s 和字典 wordDict，判断 s 是否能被拆分为字典中的单词（单词可重复使用）。

输入：s = "leetcode", wordDict = ["leet","code"]   输出：true

难点与易错点

解法一：暴力 / 直观

DFS 回溯：从当前位置尝试所有以它为起点的字典词，能匹配就继续往下走。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, 0, new HashSet<>(wordDict));
    }
    private boolean dfs(String s, int start, Set<String> dict) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++) {
            if (dict.contains(s.substring(start, end)) && dfs(s, end, dict)) {
                return true;
            }
        }
        return false;
    }
}

复杂度：每个位置都可能作为新的起点继续分支，最坏情况（如 s="aaaaa"、字典含 "a"）每个位置有 O(n) 种切法，时间 O(2^n)，栈空间 O(n)。

瓶颈：同一个 start 位置会被反复进入（不同路径到达同一 start），重叠子问题多。

解法二：优化 / 最优

状态定义：dp[i] = 字符串 s[0..i-1]（前 i 个字符）能否被拆分成字典单词。

转移方程：dp[i] = true，当且仅当存在 j ∈ [0, i-1]，使得 dp[j] == true 且 s[j..i-1] ∈ dict。

初始化：dp[0] = true（空串可拆分）。

遍历顺序：外层 i 从 1 到 n 正序，内层 j 从 0 到 i-1 正序。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict); // O(1) 查询
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 空字符串可拆分

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // dp[j] 可拆分 且 s[j..i-1] 在字典中
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一种方式就够了
                }
            }
        }

        return dp[n];
    }
}

复杂度逐步推导：外层 i 从 1 到 n 共 n 次；内层 j 从 0 到 i-1 共 i 次；每次 s.substring(j, i) 拷贝长度 i-j 的字符串，最坏 O(L)（L 为字典最长单词长度，同时也是单次 substring 的上界）。总时间 Σ(i=1..n) Σ(j=0..i-1) O(L) = O(n² × L)。空间：dp 数组 O(n)，HashSet 存字典 O(W)（W 为字典总字符数），合计 O(n + W)。

多解法对比

解法时间空间适用场景
DFS 回溯O(2^n)O(n)讲清「按起点切词」的搜索
记忆化 DFSO(n² × L)O(n + W)保留递归结构
前缀 DPO(n² × L)O(n + W)面试首选，最直观
Trie + DPO(n²)O(n + 字典)字典极大时优化 substring 查找

这题约束 n 可达 300，O(n² × L) ≈ 几十万次，完全可接受，且 DP 写法最直白、最不容易错，故选前缀 DP。

CodeTop 变体

#300 最长递增子序列

题意

给整数数组 nums，返回最长严格递增子序列的长度（子序列不一定连续）。

输入：nums = [10,9,2,5,3,7,101,18]   输出：4 （2,3,7,101）

难点与易错点

解法一：暴力 / 直观（DP O(n²)）

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

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

初始化：所有 dp[i] = 1。

class Solution {
    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 = 0; 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;
    }
}

复杂度：外层 i 共 n 次，内层 j 共 i 次，总 Σi = n(n-1)/2 次比较，时间 O(n²)，空间 O(n)。

瓶颈：对每个 i 都要向前扫一遍找「所有比它小且 dp 最大的 j」，这层 O(n) 的线性查找是瓶颈。

解法二：优化 / 最优（贪心 + 二分）

核心思想：维护 tails 数组，tails[k] = 所有长度为 k+1 的递增子序列中，末尾元素的最小值。末尾越小，后面越容易接上更大的数，这是贪心正确性的直觉来源。

三步主线：

  1. 遍历每个 num，在 tails[0..len-1] 中二分找第一个 >= num 的位置 pos。
  2. tails[pos] = num；若 pos == len，说明 num 比所有末尾都大，len++。
  3. 返回 len。
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length]; // tails[i] = 长度为 i+1 的 LIS 最小末尾
        int len = 0;

        for (int num : nums) {
            // 二分查找第一个 >= num 的位置（lower_bound）
            int l = 0, r = len;
            while (l < r) {
                int mid = l + ((r - l) >> 1);
                if (tails[mid] < num) l = mid + 1;
                else                  r = mid;
            }

            tails[l] = num; // 替换（更新最小末尾）

            if (l == len) len++; // 序列长度增加
        }

        return len;
    }
}

复杂度逐步推导：外层遍历 n 个元素共 n 次；每次在长度为 len ≤ n 的有序数组上做二分查找，比较次数 O(log len) = O(log n)。两者相乘，时间 O(n log n)。tails 数组长度 nums.length，空间 O(n)。

💭 思考：O(n²) 的 DP 为什么能优化到 O(n log n)？瓶颈在哪？——DP 版对每个 i 都要向前扫一遍找「比它小且 dp 最大的 j」，这层 O(n) 线性查找就是病灶。换个视角：我们维护的不再是「以 i 结尾的 LIS 长度」，而是「每个长度对应的最小末尾」tails。末尾越小，后面越容易接上更大的数（贪心正确性来源），于是 tails 天然单调、可以用二分定位第一个 >= num 的位置，把「找插入点」从 O(n) 压到 O(log n)。看到「递增子序列 + 内层是线性查找」时，就该想到「换状态定义 + 二分」这个套路——代价是只能求长度，求具体序列还得回到 DP。

多解法对比

解法时间空间适用场景
DP O(n²)O(n²)O(n)直观，且能回溯具体序列
贪心 + 二分O(n log n)O(n)面试首选，求长度最优

这题约束 n 可达 2500，O(n²) ≈ 625 万也能过；但 O(n log n) 更优且展示二分功底，面试官通常期待二分版。注意：贪心 + 二分只能求长度，求具体序列还得回到 DP 回溯。

CodeTop 变体

#152 乘积最大子数组

题意

给你整数数组 nums，找到乘积最大的连续子数组，返回该子数组的乘积。

输入：nums = [2,3,-2,4]   输出：6 （[2,3]）

难点与易错点

解法一：暴力 / 直观

枚举所有子数组，逐个累乘求最大。

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = i; j < n; j++) {
                prod *= nums[j];
                ans = Math.max(ans, prod);
            }
        }
        return ans;
    }
}

复杂度：外层起点 i 共 n 个，内层终点 j 从 i 到 n-1，总子数组数 n(n+1)/2，时间 O(n²)，空间 O(1)。

瓶颈：枚举了所有 O(n²) 个子数组，而很多子数组的信息其实可以复用（以同一元素结尾的子数组之间只差一个乘数）。

解法二：优化 / 最优

状态定义：maxProd = 以当前元素结尾的子数组的最大乘积，minProd = 以当前元素结尾的子数组的最小乘积（负数场景下有用）。

转移方程：maxProd = max(num, max(prevMax * num, minProd * num))；minProd = min(num, min(prevMax * num, minProd * num))。

初始化：maxProd = minProd = result = nums[0]。

遍历顺序：i 从 1 到 n-1 正序，每轮先存 prevMax 再更新。

class Solution {
    public int maxProduct(int[] nums) {
        int maxProd = nums[0];
        int minProd = nums[0];
        int result  = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];

            // 因为 maxProd 和 minProd 会互相影响，先保存 maxProd
            int prevMax = maxProd;
            // 三种情况：仅 num 自身 / 延续最大 / 延续最小（负数翻转）
            maxProd = Math.max(num, Math.max(prevMax * num, minProd * num));
            minProd = Math.min(num, Math.min(prevMax * num, minProd * num));

            result = Math.max(result, maxProd);
        }

        return result;
    }
}

复杂度逐步推导：循环 i 从 1 到 n-1 共 n-1 次，每次只做常数次乘法与比较，时间 O(n)。只用了 maxProd、minProd、result、prevMax 四个变量，空间 O(1)。

💭 思考：为什么这题不能照搬「最大子数组和」的单状态 DP，而要同时维护 max 和 min？——因为乘法和加法不同：乘以一个负数会让「最大」变「最小」、「最小」变「最大」。如果只记 maxProd，遇到负数时它没法利用「之前最小的负积」翻盘成正的最大值。所以每个位置要保留「以当前元素结尾的最大积和最小积」两个状态，候选来自三种：只取自身、延续最大、延续最小（负负得正）。看到「乘积 + 含负数」这个信号，就该联想到「正负翻转需要双状态」，并且更新顺序上要先用 prevMax 存旧值，否则 minProd 会拿被污染的新值算错。

多解法对比

解法时间空间适用场景
暴力枚举O(n²)O(1)讲清「连续子数组」枚举
双状态 DPO(n)O(1)面试首选，单遍扫描

时间 O(n) 是下界（每个元素至少看一次），空间 O(1) 最优，故选双状态 DP。

CodeTop 变体

#416 分割等和子集

题意

给定只包含正整数的非空数组 nums，判断是否可以将它分成两个子集使得两个子集的元素和相等。

输入：nums = [1,5,11,5]   输出：true （[1,5,5] 和 [11]）

难点与易错点

解法一：暴力 / 直观

DFS 回溯：每个元素选或不选，枚举所有子集。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 2 != 0) return false;
        return dfs(nums, 0, sum / 2);
    }
    private boolean dfs(int[] nums, int idx, int target) {
        if (target == 0) return true;
        if (idx == nums.length || target < 0) return false;
        // 选当前元素，或不选
        return dfs(nums, idx + 1, target - nums[idx])
            || dfs(nums, idx + 1, target);
    }
}

复杂度：每个元素两种选择，决策树高度 n，时间 O(2^n)，栈空间 O(n)。

瓶颈：指数级枚举所有子集，n 稍大（如 200）就完全不可行。

解法二：优化 / 最优

状态定义：dp[j] = 能否从当前已遍历的元素中选出若干，使它们的和恰好为 j。

转移方程：dp[j] |= dp[j - num]（不选当前 num，或选了 num 且剩余 j-num 可行）。

初始化：dp[0] = true。

遍历顺序：外层遍历每个 num，内层从 target 到 num 倒序（保证每个物品只用一次）。

class Solution {
    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; // 空集和为 0，始终可行

        for (int num : nums) {
            // 0-1 背包：倒序遍历，防止同一物品被重复使用
            for (int j = target; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }

        return dp[target];
    }
}

复杂度逐步推导：外层遍历 n 个元素共 n 次；内层 j 从 target 倒序到 num，最多 target 次。两者相乘，时间 O(n × target)，其中 target = sum/2，即 O(n × sum)。dp 数组长度 target + 1，空间 O(target)。

💭 思考：为什么「分成两半」等于「找一个子集和为 sum/2」，又为什么 0-1 背包必须倒序？——先想第一步：总和为 sum，要找两个和相等的子集，等价于找「一个子集和恰好为 sum/2」，另一半自动凑齐，这就是「能否装满背包」。再想第二步：一维 DP 里 dp[j] 依赖 dp[j - num]，若 j 正序走，算 dp[j] 时 dp[j - num] 可能已经用上了「当前这个 num」，同一物品被用多次，就退化成了完全背包；倒序走保证 dp[j - num] 还是「上一层（不含当前物品）」的旧值，每个物品只用一次。看到「每个元素只能用一次 + 装满某容量」这个信号，就锁定 0-1 背包 + 倒序。

多解法对比

解法时间空间适用场景
DFS 回溯O(2^n)O(n)讲清「选/不选」决策树
0-1 背包 DPO(n × target)O(target)面试首选

这题约束 sum 可达 2 × 10^4，O(n × sum/2) ≈ 几百万，可接受；DFS 的 2^n 在 n=200 时完全不可行。倒序一维数组已经是空间最优的 0-1 背包写法。

CodeTop 变体

#32 最长有效括号

题意

给你只含 ( 和 ) 的字符串 s，返回最长有效括号子串的长度。

输入：s = ")()())"   输出：4 （"()()"）

难点与易错点

解法一：暴力 / 直观

枚举每个起点，向右扫描维护括号平衡，平衡为 0 时更新长度，平衡为负时提前终止。

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            int balance = 0;
            for (int j = i; j < n; j++) {
                balance += (s.charAt(j) == '(' ? 1 : -1);
                if (balance < 0) break; // 右括号过多，这段不可能再有效
                if (balance == 0) maxLen = Math.max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
}

复杂度：外层起点 i 共 n 个，内层终点 j 最多 n 个，时间 O(n²)，空间 O(1)。

瓶颈：对每个起点都重新扫一遍，大量重复扫描，n 到 10^5 时 O(n²) 超时。

解法二：动态规划 O(n)

状态定义：dp[i] = 以 s[i] 结尾的最长有效括号长度（仅当 s[i] == ')' 时可能非 0）。

转移方程：

初始化：dp 全 0，maxLen = 0。

遍历顺序：i 从 1 到 n-1 正序（dp[i] 依赖 dp[i-1] 和更早位置，正序保证已算好）。

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int maxLen = 0;

        for (int i = 1; i < n; 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] - 1 >= 0
                        && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2
                            + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }

        return maxLen;
    }
}

复杂度逐步推导：单层循环 i 从 1 到 n-1 共 n-1 次，每次只做常数次下标判断和加法，时间 O(n)。dp 数组长度 n，空间 O(n)。

解法三：单调栈 O(n)（源材料最优解）

思路：栈存下标，栈底始终压着一个「最后一个无效位置」的哨兵，用 i - stack.peek() 直接得到当前有效段长度。

三步主线：

  1. 栈初始压入 -1（哨兵，表示最后一个无效下标）。
  2. 遇到 (：将下标压栈；遇到 )：弹出栈顶——
    • 若栈为空，压入当前下标作为新哨兵；
    • 若栈非空，len = i - stack.peek()，更新最大值。
  3. 返回最大有效长度。
class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1); // 哨兵：最后一个"无效"位置的下标
        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i); // 左括号下标入栈
            } else {
                stack.pop(); // 弹出与当前右括号匹配的左括号（或哨兵）

                if (stack.isEmpty()) {
                    stack.push(i); // 栈空：当前右括号无法匹配，成为新哨兵
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek()); // 合法长度
                }
            }
        }

        return maxLen;
    }
}

复杂度逐步推导：循环 i 从 0 到 n-1 共 n 次；每个下标最多入栈一次、出栈一次，均摊下来每步 O(1)。总时间 O(n)。栈最多存 n 个下标，空间 O(n)。

💭 思考：为什么栈法要在栈底压一个 -1 当「哨兵」？——一步步想：有效子串的长度 = 「当前 ) 的下标」减去「它前面最后一个无法匹配的位置」。栈里存的始终是「尚未匹配的 ( 下标」和「最近的无效右括号位置」，弹栈后 i - stack.peek() 就是当前有效段长度。若没有哨兵，当开头就是 ) 时栈会弹空，peek() 就越界；放一个 -1 作为「虚拟的最后一个无效位置」，就统一了「有效段从哪开始算」这个基准。看到「括号匹配 + 求最长有效段」，先想到「用栈下标做差」，再补上「哨兵给段一个起始基准」这个关键细节。

多解法对比

解法时间空间适用场景
暴力枚举O(n²)O(1)讲清「连续有效段」定义
动态规划O(n)O(n)面试常考，DP 思路清晰
单调栈O(n)O(n)源材料最优解，最简洁
双向扫描O(n)O(1)空间最优，进阶加分项

这题约束 n 可达 3 × 10^4，暴力 O(n²) 会超时，必须 O(n)。单调栈写法最短最不易错，是多数人的首选；若面试官再压空间，再讲双向扫描（左→右、右→左各扫一遍计数，遇 ) 多于 ( 就清零重来）。

CodeTop 变体

以上 9 题覆盖了动态规划面试的四大高频模型：斐波那契型（70）、线性选择型（198、152）、背包型（279、322、416）、字符串/序列型（139、300、32）。把它们的状态定义、转移方程、初始化、遍历顺序各说清楚一遍，动态规划这一关基本就稳了。

章末提问

追问大多落在「为什么选这个解法」「状态怎么定」「复杂度怎么推」三个方向，每个都能用「结论先行 + 因为」一句话顶住：

  1. 怎么判断一道题能不能用 DP？ —— 结论先行：看它是否同时满足「最优子结构」和「重叠子问题」。因为最优解能被拆成子问题最优解的组合（如打家劫舍的 max(dp[i-1], dp[i-2]+nums[i])），且暴力递归时同一子问题被反复计算（如爬楼梯的 dfs(n-2) 被多次调用），两者齐备才能把指数级降到多项式级。

  2. dp[i] 的状态到底怎么定义？ —— 结论先行：先问「子问题的规模是什么」，下标就是规模、值就是该规模下的答案。因为状态定义错一句，转移和初始化就全错；要能一字不差说出 dp[i] 的语义——如最长递增子序列的 dp[i] 必须限定「以 nums[i] 结尾」，否则最后还要遍历取 max 才能得到全局答案。

  3. 为什么 0-1 背包要倒序遍历、完全背包要正序？ —— 结论先行：倒序是为了保证每个物品只被用一次。因为正序遍历时 dp[j-num] 可能已经包含「当前物品」，同一物品被反复累加就退化成完全背包（如分割等和子集）；完全背包想允许物品重复，才故意正序（如零钱兑换、完全平方数）。

  4. 滚动数组为什么能省空间？ —— 结论先行：因为 dp[i] 只依赖固定数量的前序状态，旧状态用完就不再需要。所以只保留几个变量或一行数组即可，空间从 O(n) 降到 O(1)（爬楼梯、打家劫舍、乘积最大子数组），代价是要小心「更新顺序污染」——乘积最大子数组必须先存 prevMax 再更新，否则 minProd 算错。

  5. 复杂度怎么一步步推出来？ —— 结论先行：先数状态数、再数每个状态的转移代价，两者相乘。因为 DP 的时间就是「状态数 × 转移代价」，如零钱兑换有 amount 个状态、每个扫 coins 个面值，得 O(amount × len)；完全平方数内层枚举 √i 个平方数，Σ√i 近似 O(n√n)。空间数 dp 数组（或滚动变量）大小。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——多维动态规划篇（路径、回文、编辑距离）
Next Post
LeetCode Hot 100——贪心篇（买卖股票、跳跃游戏、区间划分）