动态规划

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的核心思想是：将问题分解为重叠的子问题，并存储子问题的解以避免重复计算。

动态规划的核心要素

理解动态规划，需要掌握两个核心概念：

最优子结构：问题的最优解包含子问题的最优解。这意味着我们可以通过组合子问题的最优解来构造原问题的最优解。
重叠子问题：在求解过程中，相同的子问题会被反复计算。动态规划通过存储子问题的解（记忆化），避免了重复计算。

动态规划解题步骤

解决动态规划问题通常遵循以下步骤：

定义状态：明确 dp[i] 或 dp[i][j] 代表什么含义
推导状态转移方程：找出状态之间的递推关系
确定初始条件和边界：设置起始值和边界情况
确定计算顺序：通常是从小到大、自底向上
返回结果：确定最终答案对应的状态

动态规划 vs 递归 vs 贪心

方法	特点	适用场景
递归	自顶向下，可能重复计算	子问题不重叠
动态规划	自底向上，存储子问题解	子问题重叠、有最优子结构
贪心	每步选局部最优	局部最优能推导全局最优

70. 爬楼梯 (Climbing Stairs)

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

约束条件：

1 <= n <= 45

解题思路

这是一道经典的动态规划入门题，本质上是斐波那契数列的变种。

分析问题

要到达第 n 阶，只有两种可能：

从第 n-1 阶爬 1 阶上来
从第 n-2 阶爬 2 阶上来

因此，到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数。

状态定义

dp[i] 表示爬到第 i 阶的方法数。

状态转移方程

$dp[i] = dp[i-1] + dp[i-2]$

初始条件

dp[1] = 1：只有一种方法（爬 1 阶）
dp[2] = 2：有两种方法（1+1 或 2）

图解示例

以 n = 5 为例：

阶数:    1    2    3    4    5
方法数:  1    2    3    5    8

计算过程:
dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

最终结果：8

Java 代码实现

方法一：标准动态规划（使用数组）

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        // dp[i] 表示爬到第 i 阶的方法数
        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];
    }
}

方法二：空间优化（只用两个变量）

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        // 只需要前两个状态，可以用滚动变量优化空间
        int prev1 = 1;  // dp[i-2]
        int prev2 = 2;  // dp[i-1]
        
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]
            prev1 = prev2;
            prev2 = curr;
        }
        
        return prev2;
    }
}

复杂度分析

时间复杂度：O(n)，需要遍历从 3 到 n 的每个数。

空间复杂度：

方法一：O(n)，需要一个长度为 n+1 的数组
方法二：O(1)，只使用了两个变量

为什么这题是动态规划？

这道题具有动态规划的两个核心特性：

重叠子问题：计算 dp[5] 需要 dp[4] 和 dp[3]，计算 dp[4] 又需要 dp[3] 和 dp[2]，dp[3] 被重复计算。
最优子结构：dp[5] 的解可以通过组合 dp[4] 和 dp[3] 的解得到。

118. 杨辉三角 (Pascal's Triangle)

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1：

输入：numRows = 5
输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2：

输入：numRows = 1
输出：[[1]]

约束条件：

1 <= numRows <= 30

解题思路

杨辉三角具有以下性质：

每行的第一个和最后一个元素都是 1
中间的元素等于上一行同位置元素与上一行前一位置元素之和

状态定义

dp[i][j] 表示第 i 行第 j 列的元素值。

状态转移方程

$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$

其中 j 不为 0 或 i（即不是每行的首尾元素）。

图解示例

以 numRows = 5 为例：

行号:  元素:
 0      [1]
 1      [1, 1]
 2      [1, 2, 1]      ← 2 = 1 + 1
 3      [1, 3, 3, 1]   ← 3 = 1 + 2, 3 = 2 + 1
 4      [1, 4, 6, 4, 1]  ← 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1

计算过程（第 4 行）:
dp[4][0] = 1（首元素）
dp[4][1] = dp[3][0] + dp[3][1] = 1 + 3 = 4
dp[4][2] = dp[3][1] + dp[3][2] = 3 + 3 = 6
dp[4][3] = dp[3][2] + dp[3][3] = 3 + 1 = 4
dp[4][4] = 1（尾元素）

Java 代码实现

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = 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) {
                    // 每行首尾元素为 1
                    row.add(1);
                } else {
                    // 中间元素 = 上一行同位置 + 上一行前一位置
                    int val = result.get(i - 1).get(j - 1) + result.get(i - 1).get(j);
                    row.add(val);
                }
            }
            
            result.add(row);
        }
        
        return result;
    }
}

复杂度分析

时间复杂度：O(numRows²)，需要填充 numRows 行，第 i 行有 i+1 个元素。

空间复杂度：O(numRows²)，需要存储所有元素。如果不考虑输出数组，则为 O(1)。

杨辉三角的应用

杨辉三角与组合数学密切相关：

第 n 行第 k 个元素的值等于组合数 C(n, k)
可用于计算组合数、二项式展开系数等

198. 打家劫舍 (House Robber)

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：nums = [1,2,3,1]
输出：4
解释：偷窃第 1 号房屋（金额 = 1），然后偷窃第 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4。

示例 2：

输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃第 1 号房屋（金额 = 2），偷窃第 3 号房屋（金额 = 9），然后偷窃第 5 号房屋（金额 = 1）。偷窃到的最高金额 = 2 + 9 + 1 = 12。

约束条件：

1 <= nums.length <= 100
0 <= nums[i] <= 400

解题思路

这道题的关键约束是：不能偷相邻的房屋。

分析问题

对于第 i 间房屋，有两个选择：

偷第 i 间：那么第 i-1 间不能偷，最大金额 = dp[i-2] + nums[i]
不偷第 i 间：最大金额 = dp[i-1]

取两者中的较大值。

状态定义

dp[i] 表示偷窃前 i 间房屋能获得的最大金额。

状态转移方程

$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$

初始条件

dp[0] = nums[0]：只有一间房屋，必须偷
dp[1] = max(nums[0], nums[1])：两间房屋，偷金额较大的那间

图解示例

以 nums = [2, 7, 9, 3, 1] 为例：

房屋编号:  0    1    2    3    4
金额:      2    7    9    3    1

计算过程:
dp[0] = 2（只能偷第 0 间）
dp[1] = max(2, 7) = 7（偷第 1 间更划算）
dp[2] = max(dp[1], dp[0] + nums[2]) = max(7, 2 + 9) = 11（偷第 0、2 间）
dp[3] = max(dp[2], dp[1] + nums[3]) = max(11, 7 + 3) = 11（不偷第 3 间）
dp[4] = max(dp[3], dp[2] + nums[4]) = max(11, 11 + 1) = 12（偷第 0、2、4 间）

最终结果：12

Java 代码实现

方法一：标准动态规划

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        
        // 边界处理
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);
        
        // dp[i] 表示偷窃前 i+1 间房屋的最大金额
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            // 状态转移：偷当前房屋 vs 不偷当前房屋
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[n - 1];
    }
}

方法二：空间优化

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        
        if (n == 1) return nums[0];
        
        // 只需要前两个状态
        int prev2 = nums[0];                    // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        
        for (int i = 2; i < n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

复杂度分析

时间复杂度：O(n)，只需遍历数组一次。

空间复杂度：

方法一：O(n)，需要一个长度为 n 的数组
方法二：O(1)，只使用了两个变量

为什么这道题适合动态规划？

最优子结构：前 i 间房屋的最大金额可以由前 i-1 间和前 i-2 间的结果推导
无后效性：当前状态一旦确定，之后的选择不会影响之前的状态
子问题重叠：计算 dp[i] 时需要 dp[i-1] 和 dp[i-2]，这些值会被反复使用

279. 完全平方数 (Perfect Squares)

题目描述

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

约束条件：

1 <= n <= 10^4

解题思路

这道题要求用最少的完全平方数凑出目标值 n，本质上是一个完全背包问题：我们有无限个不同面额的"硬币"（完全平方数），要用最少的硬币凑出金额 n。

方法：动态规划

定义 dp[i] 表示凑出和为 i 所需的最少完全平方数个数。

对于每个 i，我们尝试用所有可能的完全平方数 j*j 来凑：

如果用了 j*j，那么还需要凑 i - j*j
dp[i] = min(dp[i], dp[i - j*j] + 1)

初始条件：dp[0] = 0，表示凑出 0 不需要任何数。

图解示例

以 n = 12 为例：

初始化：dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
         用 n 初始化表示"无穷大"

i = 1:
  j = 1: 1*1 = 1 <= 1
    dp[1] = min(dp[1], dp[0] + 1) = min(12, 0 + 1) = 1
  dp = [0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

i = 2:
  j = 1: 1*1 = 1 <= 2
    dp[2] = min(dp[2], dp[1] + 1) = min(12, 1 + 1) = 2
  dp = [0, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

i = 3:
  j = 1: 1*1 = 1 <= 3
    dp[3] = min(dp[3], dp[2] + 1) = min(12, 2 + 1) = 3
  dp = [0, 1, 2, 3, 12, 12, 12, 12, 12, 12, 12, 12, 12]

i = 4:
  j = 1: 1*1 = 1 <= 4
    dp[4] = min(dp[4], dp[3] + 1) = min(12, 3 + 1) = 4
  j = 2: 2*2 = 4 <= 4
    dp[4] = min(dp[4], dp[0] + 1) = min(4, 0 + 1) = 1
  dp = [0, 1, 2, 3, 1, 12, 12, 12, 12, 12, 12, 12, 12]

... 省略中间计算 ...

i = 12:
  j = 1: dp[12] = min(dp[12], dp[11] + 1) = min(12, 3 + 1) = 4
  j = 2: dp[12] = min(dp[12], dp[8] + 1) = min(4, 2 + 1) = 3
  j = 3: dp[12] = min(dp[12], dp[3] + 1) = min(3, 3 + 1) = 3
  dp[12] = 3

最终结果：3
解释：12 = 4 + 4 + 4（三个完全平方数）

Java 代码实现

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示凑出和为 i 所需的最少完全平方数个数
        int[] dp = new int[n + 1];
        
        // 初始化为最大值（最多需要 n 个 1）
        Arrays.fill(dp, n);
        
        // 基础情况：凑出 0 不需要任何数
        dp[0] = 0;
        
        // 遍历每个目标值
        for (int i = 1; i <= n; i++) {
            // 尝试用每个可能的完全平方数
            for (int j = 1; j * j <= i; j++) {
                // 状态转移：用 j*j 后，还需要凑 i - j*j
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }
}

复杂度分析

时间复杂度：O(n × √n)，外层循环 n 次，内层循环最多 √n 次。

空间复杂度：O(n)，需要一个长度为 n+1 的 dp 数组。

数学优化（四平方和定理）

根据拉格朗日四平方和定理，任何正整数都可以表示为至多 4 个完全平方数的和。因此答案最多是 4。可以利用这个性质进行优化，但动态规划解法已经足够高效且容易理解。

322. 零钱兑换 (Coin Change)

题目描述

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

约束条件：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

解题思路

这是一道经典的完全背包问题。我们有无限个不同面额的"物品"（硬币），要用最少的物品凑出指定的"容量"（金额）。

方法：动态规划

定义 dp[i] 表示凑出金额 i 所需的最少硬币个数。

对于每个金额 i，我们尝试用每种硬币 coin 来凑：

如果用了面额为 coin 的硬币，那么还需要凑 i - coin
dp[i] = min(dp[i], dp[i - coin] + 1)

初始条件：dp[0] = 0，表示凑出金额 0 不需要任何硬币。

图解示例

以 coins = [1, 2, 5], amount = 11 为例：

初始化：dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
         用 amount+1 初始化表示"无穷大"

i = 1:
  coin = 1: dp[1] = min(12, dp[0] + 1) = min(12, 1) = 1
  coin = 2: 2 > 1，跳过
  coin = 5: 5 > 1，跳过
  dp = [0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]

i = 2:
  coin = 1: dp[2] = min(12, dp[1] + 1) = min(12, 2) = 2
  coin = 2: dp[2] = min(2, dp[0] + 1) = min(2, 1) = 1
  coin = 5: 5 > 2，跳过
  dp = [0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]

i = 3:
  coin = 1: dp[3] = min(12, dp[2] + 1) = min(12, 2) = 2
  coin = 2: dp[3] = min(2, dp[1] + 1) = min(2, 2) = 2
  coin = 5: 5 > 3，跳过
  dp = [0, 1, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12]

i = 4:
  coin = 1: dp[4] = min(12, dp[3] + 1) = 3
  coin = 2: dp[4] = min(3, dp[2] + 1) = 2
  coin = 5: 5 > 4，跳过
  dp = [0, 1, 1, 2, 2, 12, 12, 12, 12, 12, 12, 12]

i = 5:
  coin = 1: dp[5] = min(12, dp[4] + 1) = 3
  coin = 2: dp[5] = min(3, dp[3] + 1) = 3
  coin = 5: dp[5] = min(3, dp[0] + 1) = 1
  dp = [0, 1, 1, 2, 2, 1, 12, 12, 12, 12, 12, 12]

... 省略中间计算 ...

i = 11:
  coin = 1: dp[11] = min(12, dp[10] + 1) = 4
  coin = 2: dp[11] = min(4, dp[9] + 1) = 4
  coin = 5: dp[11] = min(4, dp[6] + 1) = 3
  dp[11] = 3

最终结果：3
解释：11 = 5 + 5 + 1（三枚硬币）

Java 代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] 表示凑出金额 i 所需的最少硬币个数
        int[] dp = new int[amount + 1];
        
        // 初始化为 amount + 1（相当于无穷大，因为最多用 amount 个 1 元硬币）
        Arrays.fill(dp, amount + 1);
        
        // 基础情况：凑出金额 0 不需要任何硬币
        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);
                }
            }
        }
        
        // 如果 dp[amount] 没有被更新，说明无法凑出该金额
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

复杂度分析

时间复杂度：O(amount × n)，其中 n 是硬币种类数。需要遍历 amount 个金额，每个金额遍历 n 种硬币。

空间复杂度：O(amount)，需要一个长度为 amount+1 的 dp 数组。

为什么初始化为 amount + 1？

这是一个常见的技巧。因为凑出金额 amount 最多需要 amount 个硬币（全用面额为 1 的硬币），所以 amount + 1 可以视为"无穷大"。如果最终 dp[amount] 仍然是 amount + 1，说明无法凑出该金额。

完全背包 vs 0-1 背包

这道题是完全背包问题，因为每种硬币可以使用无限次。与 0-1 背包的区别在于：

0-1 背包：每种物品只能用一次，内层循环需要倒序遍历
完全背包：每种物品可以用无限次，内层循环正序遍历

139. 单词拆分 (Word Break)

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释：返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入：s = "applepenapple", wordDict = ["apple", "pen"]
输出：true
解释：返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出：false

约束条件：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串互不相同

解题思路

这道题要求判断字符串能否被拆分成字典中的单词。关键在于如何定义状态和状态转移。

方法：动态规划

定义 dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）能否被拆分成字典中的单词。

对于位置 i，我们尝试找一个分割点 j：

如果 dp[j] 为 true（前 j 个字符可以拆分）
且子串 s[j..i-1] 在字典中
那么 dp[i] = true

图解示例

以 s = "leetcode", wordDict = ["leet", "code"] 为例：

初始化：dp = [true, false, false, false, false, false, false, false, false]
         dp[0] = true 表示空字符串可以被拆分

i = 1: 检查子串 s[0..0] = "l"
  j = 0: dp[0] = true, 但 "l" 不在字典中
  dp[1] = false

i = 2: 检查子串 s[0..1] = "le", s[1..1] = "e"
  j = 0: dp[0] = true, 但 "le" 不在字典中
  j = 1: dp[1] = false, 跳过
  dp[2] = false

i = 3: 检查子串 s[0..2] = "lee", s[1..2] = "ee", s[2..2] = "e"
  都不在字典中
  dp[3] = false

i = 4: 检查子串 s[0..3] = "leet", s[1..3] = "eet", ...
  j = 0: dp[0] = true, 且 "leet" 在字典中！
  dp[4] = true

i = 5: 检查子串 s[4..4] = "c", s[0..4] = "leetc", ...
  j = 4: dp[4] = true, 但 "c" 不在字典中
  dp[5] = false

i = 6: 检查子串 s[4..5] = "co", ...
  dp[6] = false

i = 7: 检查子串 s[4..6] = "cod", ...
  dp[7] = false

i = 8: 检查子串 s[4..7] = "code"
  j = 4: dp[4] = true, 且 "code" 在字典中！
  dp[8] = true

最终结果：dp[8] = true
解释：s 可以拆分为 "leet" + "code"

Java 代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将字典转为 HashSet，实现 O(1) 查找
        Set<String> wordSet = new HashSet<>(wordDict);
        
        int n = s.length();
        // dp[i] 表示前 i 个字符能否被拆分
        boolean[] dp = new boolean[n + 1];
        
        // 空字符串可以被拆分
        dp[0] = true;
        
        // 遍历每个位置
        for (int i = 1; i <= n; i++) {
            // 尝试每个分割点
            for (int j = 0; j < i; j++) {
                // 如果前 j 个字符可以拆分，且 s[j..i-1] 在字典中
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;  // 找到一种拆分方式即可
                }
            }
        }
        
        return dp[n];
    }
}

复杂度分析

时间复杂度：O(n²)，其中 n 是字符串长度。外层循环 n 次，内层循环最多 n 次，子串操作也是 O(n)，但总体可视为 O(n²)。

空间复杂度：O(n)，需要 dp 数组和存储字典的 Set。

优化：限制单词长度

字典中单词的最大长度为 20，可以利用这个约束优化内层循环：

for (int j = Math.max(0, i - 20); j < i; j++) {
    // 只检查长度不超过 20 的子串
}

这样时间复杂度优化为 O(n × maxLen)，其中 maxLen 是字典中单词的最大长度。

300. 最长递增子序列 (Longest Increasing Subsequence)

题目描述

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

约束条件：

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

**进阶：**你能将算法的时间复杂度降低到 O(n log n) 吗？

解题思路

这道题要求找最长严格递增子序列（LIS）的长度，是动态规划的经典问题。

方法一：动态规划 O(n²)

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

对于每个 i，我们需要检查所有 j < i：

如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 后面
dp[i] = max(dp[i], dp[j] + 1)

初始条件：每个元素自身构成长度为 1 的子序列，所以 dp[i] = 1。

方法二：贪心 + 二分查找 O(n log n)

维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。

遍历数组，对于每个元素 num：

如果 num 大于 tails 的最后一个元素，直接追加
否则，用二分查找找到 tails 中第一个大于等于 num 的位置并替换

这样做的原理：让子序列的末尾元素尽可能小，为后续元素腾出更多空间。

图解示例

方法一（动态规划）：以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：

初始状态：dp = [1, 1, 1, 1, 1, 1, 1, 1]

i = 0: nums[0] = 10
  没有前面的元素，dp[0] = 1

i = 1: nums[1] = 9
  j = 0: nums[0] = 10 > 9，不满足递增
  dp[1] = 1

i = 2: nums[2] = 2
  j = 0: 10 > 2，跳过
  j = 1: 9 > 2，跳过
  dp[2] = 1

i = 3: nums[3] = 5
  j = 0: 10 > 5，跳过
  j = 1: 9 > 5，跳过
  j = 2: 2 < 5，dp[3] = max(1, dp[2]+1) = 2
  dp[3] = 2

i = 4: nums[4] = 3
  j = 2: 2 < 3，dp[4] = max(1, dp[2]+1) = 2
  j = 3: 5 > 3，跳过
  dp[4] = 2

i = 5: nums[5] = 7
  j = 2: 2 < 7，dp[5] = max(1, 1+1) = 2
  j = 3: 5 < 7，dp[5] = max(2, 2+1) = 3
  j = 4: 3 < 7，dp[5] = max(3, 2+1) = 3
  dp[5] = 3

i = 6: nums[6] = 101
  前面所有都比 101 小
  dp[6] = max(dp[0..5]) + 1 = 3 + 1 = 4

i = 7: nums[7] = 18
  j = 5: 7 < 18，dp[7] = max(1, 3+1) = 4
  dp[7] = 4

最终结果：max(dp) = 4

方法二（贪心 + 二分）：

nums = [10, 9, 2, 5, 3, 7, 101, 18]
tails = []

num = 10: tails = [10]
num = 9:  替换 10，tails = [9]
num = 2:  替换 9，tails = [2]
num = 5:  追加，tails = [2, 5]
num = 3:  替换 5，tails = [2, 3]
num = 7:  追加，tails = [2, 3, 7]
num = 101: 追加，tails = [2, 3, 7, 101]
num = 18: 替换 101，tails = [2, 3, 7, 18]

最终结果：len(tails) = 4

Java 代码实现

方法一：动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int[] dp = new int[n];
        
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            // 初始化：每个元素自身构成长度为 1 的子序列
            dp[i] = 1;
            
            // 检查所有前面的元素
            for (int j = 0; j < i; j++) {
                // 如果可以接在 nums[j] 后面
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

方法二：贪心 + 二分查找

class Solution {
    public int lengthOfLIS(int[] nums) {
        // tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 二分查找第一个大于等于 num 的位置
            int left = 0, right = tails.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 如果 num 比所有元素都大，追加
            if (left == tails.size()) {
                tails.add(num);
            } else {
                // 否则替换第一个大于等于 num 的元素
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
}

复杂度分析

方法一：

时间复杂度：O(n²)，两层嵌套循环
空间复杂度：O(n)，需要 dp 数组

方法二：

时间复杂度：O(n log n)，每个元素进行一次二分查找
空间复杂度：O(n)，最坏情况下 tails 数组长度为 n

为什么贪心策略有效？

关键思想：让子序列的末尾元素尽可能小。

假设有两个长度相同的递增子序列，末尾元素分别是 5 和 8。对于后续的元素，末尾为 5 的子序列能接纳更多的元素（如 6、7 都能接在 5 后面但不能接在 8 后面）。

因此，维护每种长度子序列的最小末尾，能最大化后续的可扩展性。

152. 乘积最大子数组 (Maximum Product Subarray)

题目描述

给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个32 位整数。

示例 1：

输入：nums = [2,3,-2,4]
输出：6
解释：子数组 [2,3] 乘积最大，为 6。

示例 2：

输入：nums = [-2,0,-1]
输出：0
解释：结果不能为 2，因为 [-2,-1] 不是子数组。

示例 3：

输入：nums = [-2,3,-4]
输出：24
解释：子数组 [-2,3,-4] 乘积最大，为 24。

约束条件：

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都保证是一个 32 位整数

解题思路

这道题与"最大子数组和"类似，但有一个关键区别：负数 × 负数 = 正数。这意味着：

当前最大值乘以负数会变成最小值
当前最小值乘以负数会变成最大值

因此，我们需要同时维护最大值和最小值。

方法：动态规划

定义两个状态：

maxProd：以当前位置结尾的子数组的最大乘积
minProd：以当前位置结尾的子数组的最小乘积

对于每个元素 nums[i]：

如果 nums[i] 是正数：maxProd 和 minProd 都乘以 nums[i]
如果 nums[i] 是负数：maxProd 和 minProd 交换后乘以 nums[i]
如果 nums[i] 是 0：最大最小都变为 0，但可能需要重新开始

状态转移： $maxProd = \max(nums[i], maxProd \times nums[i], minProd \times nums[i])$ $minProd = \min(nums[i], maxProd \times nums[i], minProd \times nums[i])$

图解示例

以 nums = [2, 3, -2, 4] 为例：

初始状态：maxProd = 2, minProd = 2, result = 2

i = 1, nums[1] = 3:
  maxProd = max(3, 2×3, 2×3) = max(3, 6, 6) = 6
  minProd = min(3, 2×3, 2×3) = min(3, 6, 6) = 3
  result = max(2, 6) = 6

i = 2, nums[2] = -2 (负数，先交换):
  交换 maxProd 和 minProd：maxProd = 3, minProd = 6
  maxProd = max(-2, 3×(-2), 6×(-2)) = max(-2, -6, -12) = -2
  minProd = min(-2, 3×(-2), 6×(-2)) = min(-2, -6, -12) = -12
  result = max(6, -2) = 6

i = 3, nums[3] = 4:
  maxProd = max(4, (-2)×4, (-12)×4) = max(4, -8, -48) = 4
  minProd = min(4, (-2)×4, (-12)×4) = min(4, -8, -48) = -48
  result = max(6, 4) = 6

最终结果：6
解释：最大乘积子数组是 [2, 3]，乘积为 6

以 nums = [-2, 3, -4] 为例（展示负负得正）：

初始状态：maxProd = -2, minProd = -2, result = -2

i = 1, nums[1] = 3:
  maxProd = max(3, (-2)×3, (-2)×3) = max(3, -6, -6) = 3
  minProd = min(3, (-2)×3, (-2)×3) = min(3, -6, -6) = -6
  result = max(-2, 3) = 3

i = 2, nums[2] = -4 (负数，先交换):
  交换：maxProd = -6, minProd = 3
  maxProd = max(-4, (-6)×(-4), 3×(-4)) = max(-4, 24, -12) = 24
  minProd = min(-4, (-6)×(-4), 3×(-4)) = min(-4, 24, -12) = -12
  result = max(3, 24) = 24

最终结果：24
解释：整个数组 [-2, 3, -4] 的乘积为 24（负负得正）

Java 代码实现

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++) {
            // 如果当前元素是负数，交换最大最小值
            // 因为负数会让大数变小，小数变大
            if (nums[i] < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }
            
            // 更新最大最小值
            // 选择：重新开始 vs 继续前面的子数组
            maxProd = Math.max(nums[i], maxProd * nums[i]);
            minProd = Math.min(nums[i], minProd * nums[i]);
            
            // 更新全局结果
            result = Math.max(result, maxProd);
        }
        
        return result;
    }
}

复杂度分析

时间复杂度：O(n)，只需遍历数组一次。

空间复杂度：O(1)，只使用了常数个变量。

为什么需要维护最小值？

因为负数的存在，当前的最小乘积在遇到另一个负数后可能变成最大乘积。

例如 [-2, 3, -4]：

遍历到 3 时，minProd = -6
遍历到 -4 时，minProd * (-4) = 24 成为最大值

如果只维护最大值，就会错过这种情况。

与最大子数组和的区别

问题	特点	状态
最大子数组和	加法满足单调性	只需维护一个最大值
最大乘积子数组	乘法有负负得正	需要同时维护最大和最小值

416. 分割等和子集 (Partition Equal Subset Sum)

题目描述

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

约束条件：

1 <= nums.length <= 200
1 <= nums[i] <= 100

解题思路

这道题的本质是：能否从数组中选出若干元素，使其和恰好等于总和的一半。这是一个经典的0-1 背包问题。

关键观察

如果数组总和是奇数，一定不能平分，直接返回 false
设 target = sum / 2，问题转化为：能否选出若干元素，使其和恰好为 target

方法：动态规划

定义 dp[j] 表示能否选出若干元素使其和恰好为 j。

对于每个元素 num，从大到小遍历 j：

dp[j] = dp[j] || dp[j - num]

初始条件：dp[0] = true，表示选择 0 个元素时和为 0。

图解示例

以 nums = [1, 5, 11, 5] 为例：

第一步：计算总和
sum = 1 + 5 + 11 + 5 = 22
target = 22 / 2 = 11

第二步：初始化
dp = [true, false, false, false, false, false, false, false, false, false, false, false]
      索引:  0     1     2     3     4     5     6     7     8     9    10    11

第三步：处理每个元素（倒序遍历）

处理 num = 1:
  j = 11: dp[11] = dp[11] || dp[10] = false || false = false
  j = 10: dp[10] = dp[10] || dp[9] = false || false = false
  ...
  j = 1: dp[1] = dp[1] || dp[0] = false || true = true
  dp = [T, T, F, F, F, F, F, F, F, F, F, F]

处理 num = 5:
  j = 11: dp[11] = dp[11] || dp[6] = false || false = false
  j = 10: dp[10] = dp[10] || dp[5] = false || false = false
  j = 9: dp[9] = dp[9] || dp[4] = false || false = false
  j = 8: dp[8] = dp[8] || dp[3] = false || false = false
  j = 7: dp[7] = dp[7] || dp[2] = false || false = false
  j = 6: dp[6] = dp[6] || dp[1] = false || true = true
  j = 5: dp[5] = dp[5] || dp[0] = false || true = true
  dp = [T, T, F, F, F, T, T, F, F, F, F, F]

处理 num = 11:
  j = 11: dp[11] = dp[11] || dp[0] = false || true = true ← 找到答案！
  
此时 dp[11] = true，说明可以分割

处理 num = 5（虽然已经找到答案，但继续演示）:
  j = 11: dp[11] = dp[11] || dp[6] = true || true = true
  ...

最终结果：dp[11] = true
解释：可以选择 [1, 5, 5] = 11 或 [11] = 11

Java 代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        // 计算数组总和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // 如果总和是奇数，无法平分
        if (sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        
        // dp[j] 表示能否选出若干元素使其和恰好为 j
        boolean[] dp = new boolean[target + 1];
        
        // 初始条件：选择 0 个元素时和为 0
        dp[0] = true;
        
        // 0-1 背包：每个元素只能用一次
        for (int num : nums) {
            // 必须倒序遍历，避免重复使用当前元素
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

复杂度分析

时间复杂度：O(n × target)，其中 n 是数组长度，target 是目标和（总和的一半）。

空间复杂度：O(target)，使用一维 dp 数组。

为什么必须倒序遍历？

这是 0-1 背包问题的关键。如果正序遍历：

假设 num = 2, target = 4
正序遍历：
  j = 2: dp[2] = dp[2] || dp[0] = true  （用了 num）
  j = 4: dp[4] = dp[4] || dp[2] = true  （又用了 num，重复使用！）

倒序遍历：
  j = 4: dp[4] = dp[4] || dp[2] = false（此时 dp[2] 还没更新）
  j = 2: dp[2] = dp[2] || dp[0] = true

倒序遍历保证每个元素在每个容量下最多被使用一次。

与完全背包的区别

问题类型	特点	遍历顺序
0-1 背包	每个物品只能用一次	倒序
完全背包	每个物品可以用无限次	正序

32. 最长有效括号 (Longest Valid Parentheses)

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

约束条件：

0 <= s.length <= 3 * 10^4
s[i] 为 '(' 或 ')'

解题思路

这道题要求找最长的有效括号子串。有效括号子串是指括号完全匹配且连续的子串。

方法一：栈

使用栈来匹配括号，栈中存储下标：

初始时压入 -1 作为"垫脚石"，用于计算长度
遇到 '('：压入当前下标
遇到 ')'：弹栈
- 如果弹栈后栈为空，压入当前下标（作为新的垫脚石）
- 如果栈不为空，当前有效长度 = 当前下标 - 栈顶下标

方法二：动态规划

定义 dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度。

如果 s[i] == '('：dp[i] = 0（以 '(' 结尾不可能是有效括号）
如果 s[i] == ')'：
- 如果 s[i-1] == '('：形成 "()"，dp[i] = dp[i-2] + 2
- 如果 s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('：形成 "(...))"，dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

图解示例

方法一（栈）：以 s = ")()())" 为例：

初始：stack = [-1]

i = 0, s[0] = ')':
  弹栈：stack = []
  栈为空，压入当前下标
  stack = [0]

i = 1, s[1] = '(':
  压栈：stack = [0, 1]

i = 2, s[2] = ')':
  弹栈：stack = [0]
  栈不为空，长度 = 2 - 0 = 2
  maxLen = 2

i = 3, s[3] = '(':
  压栈：stack = [0, 3]

i = 4, s[4] = ')':
  弹栈：stack = [0]
  栈不为空，长度 = 4 - 0 = 4
  maxLen = 4

i = 5, s[5] = ')':
  弹栈：stack = []
  栈为空，压入当前下标
  stack = [5]

最终结果：4

方法二（动态规划）：以 s = "()(())" 为例：

初始：dp = [0, 0, 0, 0, 0, 0]

i = 1, s[1] = ')', s[0] = '(':
  形成 "()"，dp[1] = dp[-1] + 2 = 0 + 2 = 2
  dp = [0, 2, 0, 0, 0, 0]

i = 2, s[2] = '(':
  dp[2] = 0
  dp = [0, 2, 0, 0, 0, 0]

i = 3, s[3] = '(':
  dp[3] = 0
  dp = [0, 2, 0, 0, 0, 0]

i = 4, s[4] = ')', s[3] = '(':
  形成 "()"，dp[4] = dp[2] + 2 = 0 + 2 = 2
  dp = [0, 2, 0, 0, 2, 0]

i = 5, s[5] = ')', s[4] = ')':
  s[4] = ')'，检查 s[5 - dp[4] - 1] = s[2] = '('
  匹配！形成 "(())"
  dp[5] = dp[4] + 2 + dp[5 - dp[4] - 2] = 2 + 2 + dp[1] = 4 + 2 = 6
  dp = [0, 2, 0, 0, 2, 6]

最终结果：max(dp) = 6
整个字符串 "()(())" 都是有效括号

Java 代码实现

方法一：栈

class Solution {
    public int longestValidParentheses(String s) {
        // 使用栈存储下标
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 初始压入 -1 作为垫脚石
        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;
    }
}

方法二：动态规划

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n <= 1) return 0;
        
        // dp[i] 表示以 s[i] 结尾的最长有效括号长度
        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 {
                    // 形式 "....))"
                    // 检查与当前 ')' 匹配的 '(' 是否存在
                    int prevLen = dp[i - 1];
                    int matchIndex = i - prevLen - 1;
                    
                    if (matchIndex >= 0 && s.charAt(matchIndex) == '(') {
                        // 匹配成功
                        dp[i] = dp[i - 1] + 2 + (matchIndex >= 1 ? dp[matchIndex - 1] : 0);
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        
        return maxLen;
    }
}

复杂度分析

方法一（栈）：

时间复杂度：O(n)，每个元素最多入栈出栈各一次
空间复杂度：O(n)，栈最多存储 n 个元素

方法二（动态规划）：

时间复杂度：O(n)，遍历一次
空间复杂度：O(n)，需要 dp 数组

栈方法的关键思想

为什么要初始压入 -1？

-1 作为一个虚拟的"最后一个未匹配的右括号"位置
当遇到有效括号时，长度 = 当前位置 - 上一个未匹配位置
如果没有 -1，第一个 "()" 无法正确计算长度

动态规划的核心要素​

动态规划解题步骤​

动态规划 vs 递归 vs 贪心​

题目描述​

解题思路​

分析问题​

状态定义​

状态转移方程​

初始条件​

图解示例​

Java 代码实现​

复杂度分析​

为什么这题是动态规划？​

相关题目​

题目描述​

解题思路​

状态定义​

状态转移方程​

图解示例​

Java 代码实现​

复杂度分析​

杨辉三角的应用​

相关题目​

题目描述​

解题思路​

分析问题​

状态定义​

状态转移方程​

初始条件​

图解示例​

Java 代码实现​

复杂度分析​

为什么这道题适合动态规划？​

相关题目​

题目描述​

解题思路​

方法：动态规划​

图解示例​

Java 代码实现​

复杂度分析​

数学优化（四平方和定理）​

相关题目​

题目描述​

解题思路​

方法：动态规划​

图解示例​

Java 代码实现​

复杂度分析​

为什么初始化为 amount + 1？​

完全背包 vs 0-1 背包​

相关题目​

题目描述​

解题思路​

方法：动态规划​

图解示例​

Java 代码实现​

复杂度分析​

优化：限制单词长度​

相关题目​

题目描述​

解题思路​

方法一：动态规划 O(n²)​

方法二：贪心 + 二分查找 O(n log n)​

图解示例​

Java 代码实现​

复杂度分析​

为什么贪心策略有效？​

相关题目​

题目描述​

解题思路​

方法：动态规划​

图解示例​

Java 代码实现​

复杂度分析​

为什么需要维护最小值？​

与最大子数组和的区别​

相关题目​

题目描述​

解题思路​

关键观察​

动态规划的核心要素

动态规划解题步骤

动态规划 vs 递归 vs 贪心

题目描述

解题思路

分析问题

状态定义

状态转移方程

初始条件

图解示例

Java 代码实现

复杂度分析

为什么这题是动态规划？

相关题目

题目描述

解题思路

状态定义

状态转移方程

图解示例

Java 代码实现

复杂度分析

杨辉三角的应用

相关题目

题目描述

解题思路

分析问题

状态定义

状态转移方程

初始条件

图解示例

Java 代码实现

复杂度分析

为什么这道题适合动态规划？

相关题目

题目描述

解题思路

方法：动态规划

图解示例

Java 代码实现

复杂度分析

数学优化（四平方和定理）

相关题目

题目描述

解题思路

方法：动态规划

图解示例

Java 代码实现

复杂度分析

为什么初始化为 amount + 1？

完全背包 vs 0-1 背包

相关题目

题目描述

解题思路

方法：动态规划

图解示例

Java 代码实现

复杂度分析

优化：限制单词长度

相关题目

题目描述

解题思路

方法一：动态规划 O(n²)

方法二：贪心 + 二分查找 O(n log n)

图解示例

Java 代码实现

复杂度分析

为什么贪心策略有效？

相关题目

题目描述

解题思路

方法：动态规划

图解示例

Java 代码实现

复杂度分析

为什么需要维护最小值？

与最大子数组和的区别

相关题目

题目描述

解题思路

关键观察