《LeetCode 动态规划 (基础版)》整整 50 题量大管饱题解套餐

LeetCode 动态规划 (基础版)

1、斐波那契数列

Q1、爬楼梯

1、题目描述

假设你正在爬楼梯。需要 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

2、解题思路

1. 动态规划法（最优解）

• 核心思想：到达第n阶楼梯的方法数等于到达第n-1阶和第n-2阶方法数之和（斐波那契数列）
• 状态转移方程：dp[n] = dp[n-1] + dp[n-2]
• 边界条件：dp[0] = 1, dp[1] = 1

2. 空间优化动态规划

• 优化思路：只需要保存前两个状态，无需存储整个数组

• 变量定义 ：

  • p: dp[i-2]
  • q: dp[i-1]
  • r: dp[i]

3、代码实现

C++

// 方法1: 基础动态规划class Solution {public: int climbStairs(int n) { if (n <= 1) { return 1; // 边界情况处理 } vector dp(n + 1); dp[0] = dp[1] = 1; // 初始条件 for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移 } return dp[n]; // 返回结果 }};

// 方法2: 空间优化动态规划class Solution {public: int climbStairs(int n) { if (n <= 1) { return 1; // 边界情况处理 } int p = 0, q = 0, r = 1; // 初始化变量 for (int i = 1; i <= n; ++i) { p = q; // dp[i-2] q = r; // dp[i-1] r = p + q; // dp[i] = dp[i-1] + dp[i-2] } return r; // 返回结果 }};

Java

// 方法1: 基础动态规划class Solution { public int climbStairs(int n) { if (n <= 1) { return 1; } int[] dp = new int[n + 1]; dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}

// 方法2: 空间优化动态规划class Solution { public int climbStairs(int n) { if (n <= 1) { return 1; } int p = 0, q = 0, r = 1; for (int i = 1; i <= n; i++) { p = q; q = r; r = p + q; } return r; }}

Python

# 方法1: 基础动态规划class Solution: def climbStairs(self, n: int) -> int: if n <= 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

# 方法2: 空间优化动态规划class Solution: def climbStairs(self, n: int) -> int: if n <= 1: return 1 p, q, r = 0, 0, 1 for _ in range(1, n + 1): p, q = q, r r = p + q return r

4、复杂度分析

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

• 空间复杂度：

  • 基础DP：O(n)，需要存储整个数组
  • 优化DP：O(1)，仅需常数空间

Q2、斐波那契数

1、题目描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

2、解题思路

1. 递归法（最直观但效率低）

• 核心思想：直接按照定义递归计算
• 问题：存在大量重复计算，时间复杂度O(2^n)

2. 记忆化递归（优化递归）

• 核心思想：使用数组存储已计算的结果，避免重复计算
• 优点：时间复杂度降为O(n)，空间复杂度O(n)

3. 动态规划（迭代法）

• 核心思想：自底向上计算，从F(0)和F(1)开始逐步计算到F(n)
• 优点：时间复杂度O(n)，空间复杂度O(n)

4. 空间优化动态规划

• 核心思想：只保存前两个状态，减少空间使用
• 优点：时间复杂度O(n)，空间复杂度O(1)

3、代码实现

C++

// 方法1: 递归法(不推荐)class Solution {public: int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fib(n - 1) + fib(n - 2); // 递归调用 }};

// 方法2: 记忆化递归class Solution {private: int memo[31]; // 记忆化数据, n 最大为 30public: int fib(int n) { memset(memo, -1, sizeof(memo)); // 初始化为 -1 memo[0] = 0, memo[1] = 1; return dfs(n); } int dfs(int n) { if (memo[n] != -1) { return memo[n]; // 已计算过, 直接返回 } memo[n] = dfs(n - 1) + dfs(n - 2); // 计算并存储 return memo[n]; }};

// 方法3: 动态规划class Solution {public: int fib(int n) { if (n <= 1) { return n; } int dp[31] = {0}; // 初始化数组 dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移 } return dp[n]; }};

// 方法4: 空间优化动态规划class Solution {public: int fib(int n) { if (n <= 1) { return n; } int p = 0, q = 1, r = 1; // 初始化三个变量 for (int i = 2; i <= n; ++i) { r = p + q; // 计算当前值 p = q; // 更新前一个值 q = r; // 更新当前值 } return r; }};

Java

class Solution { public int fib(int n) { if (n <= 1) { return n; } int p = 0, q = 1, r = 1; for (int i = 2; i <= n; i++) { r = p + q; p = q; q = r; } return r; }}

Python

class Solution: def fib(self, n: int) -> int: if n <= 1: return n p, q, r = 0, 1, 1 for _ in range(2, n + 1): r = p + q p, q = q, r return r

4、复杂度分析

方法 时间复杂度 空间复杂度 递归法 O(2ⁿ) O(n) 记忆化递归 O(n) O(n) 动态规划 O(n) O(n) 优化动态规划 O(n) O(1)

Q3、第 N 个泰波那契数

1、题目描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4输出：4解释：T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25输出：1389537

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

2、解题思路

1. 递归法（不推荐）

• 直接按照定义递归计算
• 时间复杂度O(3^n)，效率极低

2. 记忆化递归

• 使用数组存储已计算结果
• 时间复杂度O(n)，空间复杂度O(n)

3. 动态规划（迭代法）

• 自底向上计算
• 时间复杂度O(n)，空间复杂度O(n)

4. 空间优化动态规划（推荐）

• 只保存前三个状态
• 时间复杂度O(n)，空间复杂度O(1)

3、代码实现

C++

// 方法1: 递归法 (不推荐) (超出时间限制)class Solution {public: int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); }};

// 方法2: 记忆化递归class Solution {private: int memo[38] = {0}; // n 最大为 37public: int tribonacci(int n) { if (memo[n] != 0 || n == 0) { return memo[n]; } if (n == 1 || n == 2) { return memo[n] = 1; } return memo[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); }};

// 方法3: 动态规划class Solution {public: int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } int dp[38] = {0}; dp[0] = 0; dp[1] = dp[2] = 1; for (int i = 3; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } return dp[n]; }};

// 方法4: 动态规划空间优化class Solution {public: int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } int p = 0, q = 1, r = 1, s = 0; for (int i = 3; i <= n; ++i) { s = p + q + r; p = q; q = r; r = s; } return r; }};

Java

class Solution { public int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } int p = 0, q = 1, r = 1; for (int i = 3; i <= n; i++) { int s = p + q + r; p = q; q = r; r = s; } return r; }}

Python

class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 if n == 1 or n == 2: return 1 p, q, r = 0, 1, 1 for _ in range(3, n+1): s = p + q + r p, q, r = q, r, s return r

4、复杂度分析

方法 时间复杂度 空间复杂度 递归法 O(3ⁿ) O(n) 记忆化递归 O(n) O(n) 动态规划 O(n) O(n) 优化动态规划 O(n) O(1)

Q4、使用最小花费爬楼梯

1、题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]输出：15解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]输出：6解释：你将从下标为 0 的台阶开始。- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。- 支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

2、解题思路

1. 动态规划（自底向上）

• 状态定义：dp[i]表示从第i个台阶出发到达顶部的最小花费
• 转移方程：dp[i] = cost[i] + min(dp[i+1], dp[i+2])
• 初始条件：dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]
• 结果：min(dp[0], dp[1])

2. 动态规划（自顶向下）

• 状态定义：dp[i]表示到达第i个台阶的最小总花费
• 转移方程：dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• 初始条件：dp[0] = cost[0], dp[1] = cost[1]
• 结果：min(dp[n-1], dp[n-2])

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int minCostClimbingStairs(vector& cost) { int n = cost.size(); vector dp(n, 0); // dp 数组 // 初始化最后两个台阶 dp[n - 1] = cost[n - 1]; dp[n - 2] = cost[n - 2]; // 从后往前计算每个台阶的最小花费 for (int i = n - 3; i >= 0; --i) { dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]); // 取跳 1 步或 2 步的最小值 } // 可以从第 0 或者第 1 个台阶开始 return min(dp[0], dp[1]); }};

// 方法2： 动态规划class Solution {public: int minCostClimbingStairs(vector& cost) { int n = cost.size(); vector dp(n, 0); // dp 数组 // 初始化前两个台阶 dp[0] = cost[0]; dp[1] = cost[1]; // 从前往后计算每个台阶的最小花费 for (int i = 2; i < n; ++i) { dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]); // 取前 1 步或前 2 步的最小值 } // 最后可以从倒数第 1 或第 2 个台阶跳到顶部 return min(dp[n - 1], dp[n - 2]); }};

// 方法3： 动态规划空间优化class Solution {public: int minCostClimbingStairs(vector& cost) { int n = cost.size(); int prev1 = cost[0]; int prev2 = cost[1]; for (int i = 2; i < n; ++i) { int current = cost[i] + min(prev1, prev2); // 当前台阶的最小花费 prev1 = prev2; prev2 = current; } return min(prev1, prev2); }};

Java

class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int prev2 = cost[0]; int prev1 = cost[1]; for (int i = 2; i < n; i++) { int current = cost[i] + Math.min(prev1, prev2); prev2 = prev1; prev1 = current; } return Math.min(prev1, prev2); }}

Python

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) prev2, prev1 = cost[0], cost[1] for i in range(2, n): current = cost[i] + min(prev1, prev2) prev2, prev1 = prev1, current return min(prev1, prev2)

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(n)，需要存储dp数组（可优化为O(1)）

Q5、打家劫舍

1、题目描述

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

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

示例 1：

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

示例 2：

输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

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

2、解题思路

动态规划解法

1. 状态定义：dp[i]表示偷窃到第i个房屋时能获得的最大金额
2. 转移方程 ：
   • 如果偷第i个房屋：dp[i] = dp[i-2] + nums[i]
   • 如果不偷第i个房屋：dp[i] = dp[i-1]
   • 取两者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 初始条件 ：
   • dp[0] = nums[0]（只有一间房屋）
   • dp[1] = max(nums[0], nums[1])（两间房屋取较大值）

空间优化

• 只需要保存前两个状态(first和second)，可将空间复杂度从O(n)降为O(1)

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int rob(vector& nums) { if (nums.empty()) { return 0; } int n = nums.size(); if (n == 1) { return nums[0]; } vector dp(n, 0); dp[0] = nums[0];  // 只有一间房屋的情况 dp[1] = max(nums[0], nums[1]); // 两间房屋取较大值 for (int i = 2; i < n; ++i) { // 当前最大值 = max(不偷当前房屋的最大值, 偷当前房屋的最大值) dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[n - 1]; }};

// 方法2: 动态规划空间优化class Solution {public: int rob(vector& nums) { if (nums.empty()) { return 0; } int n = nums.size(); if (n == 1) { return nums[0]; } int first = nums[0]; // 前前一个房屋的最大值 int second = max(nums[0], nums[1]); // 前一个房屋的最大值 for (int i = 2; i < n; ++i) { int tmp = second; second = max(first + nums[i], second); // 更新当前最大值 first = tmp; } return second; }};

Java

class Solution { public int rob(int[] nums) { if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } int first = nums[0]; int second = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; }}

Python

class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1: return nums[0] first = nums[0] second = max(nums[0], nums[1]) for i in range(2, len(nums)): current = max(first + nums[i], second) first, second = second, current return second

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了常数个额外空间

Q6、删除并获得点数

1、题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2]输出：6解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4]输出：9解释：删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

2、解题思路

这个问题可以转化为类似于 “打家劫舍” 问题的变种：

1. 首先统计每个数字出现的总和（类似房屋金额）
2. 然后不能选择相邻的数字（类似于不能偷相邻房屋）
3. 使用动态规划求解最大点数

具体步骤

1. 统计点数：创建一个数组sum，其中sum[i]表示所有等于i的元素的总和

2. 动态规划 ：

   • dp[i]表示处理到数字i时能获得的最大点数
   • dp[i] = max(dp[i-1], dp[i-2] + sum[i])

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int deleteAndEarn(vector& nums) { const int N = 10001; // 题目中 nums[i] 最大为 10000 vector sum(N, 0); // 统计每个数字的总和 // 填充 sum 数组 for (int num : nums) { sum[num] += num; } // 动态规划 vector dp(N, 0); dp[0] = sum[0]; dp[1] = max(sum[0], sum[1]); for (int i = 2; i < N; ++i) { dp[i] = max(dp[i - 1], dp[i - 2] + sum[i]); } return dp[N - 1]; }};

// 方法2: 动态规划空间优化class Solution {public: // 空间优化的 \"打家劫舍\" 解法 int deleteAndEarn(vector& nums) { // 找到数组中最大的值 int maxVal = *max_element(nums.begin(), nums.end()); // 创建并填充 sum 数组 vector sum(maxVal + 1, 0); for (int num : nums) { sum[num] += num; } // 使用优化的打家劫舍解法 return rob(sum); }private: // 空间优化的 \"打家劫舍\" 解法 int rob(vector& nums) { int n = nums.size(); if (n == 1) { return nums[0]; } int first = nums[0]; int second = max(nums[0], nums[1]); for (int i = 2; i < n; ++i) { int tmp = second; second = max(first + nums[i], second); first = tmp; } return second; }};

Java

class Solution { public int deleteAndEarn(int[] nums) { int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } int[] sum = new int[maxVal + 1]; for (int num : nums) { sum[num] += num; } return rob(sum); } private int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } int first = nums[0]; int second = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; }}

Python

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: def rob(nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] first, second = nums[0], max(nums[0], nums[1]) for i in range(2, n): first, second = second, max(first + nums[i], second) return second max_val = max(nums) if nums else 0 sum_nums = [0] * (max_val + 1) for num in nums: sum_nums[num] += num return rob(sum_nums)

4、复杂度分析

• 时间复杂度：O(n + m)，其中n是nums长度，m是nums中的最大值
• 空间复杂度：O(m)，用于存储sum数组

2、矩阵

Q7、不同路径

1、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7输出：28

示例 2：

输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3输出：28

示例 4：

输入：m = 3, n = 3输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

2、解题思路

1. 动态规划（自底向上）

• 状态定义：dp[i][j]表示到达(i,j)位置的路径数
• 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 初始条件 ：
  • 第一行和第一列的所有位置都只有1条路径（一直向右或一直向下）
• 结果：dp[m-1][n-1]

2. 记忆化搜索（自顶向下）

• 使用递归分解问题

• 记忆已经计算过的子问题避免重复计算

• 基本情况：

  • 到达起点(1,1)返回1
  • 超出边界返回0

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int uniquePaths(int m, int n) { // 创建 m x n 的 DP 表, 初始化为 1 (第一行和第一列都是 1) vector<vector> dp(m, vector(n, 1)); // 填充 DP 表 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]; }};

// 方法2: 动态规划优化class Solution {public: int uniquePaths(int m, int n) { // 只需要保存前一行的信息 vector dp(n, 1); for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { // dp[j] = 上方路径数(dp[j]) + 左方路径数(dp[j-1]) dp[j] += dp[j - 1]; } } return dp[n - 1]; }};

// 方法3: 记忆化搜索class Solution {public: int uniquePaths(int m, int n) { // 创建记忆化表, 初始化为 0 vector<vector> memo(m + 1, vector(n + 1, 0)); return dfs(m, n, memo); }private: int dfs(int i, int j, vector<vector>& memo) { // 如果已经计算过, 直接返回结果 if (memo[i][j] != 0) { return memo[i][j]; } // 边界条件: 超出网格返回 0 if (i == 0 || j == 0) { return 0; } // 基本情况: 到达起点 if (i == 1 && j == 1) { memo[i][j] = 1; return 1; } // 递归计算上方和右方的路径数之和 memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo); return memo[i][j]; }};

Java

class Solution { 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 - 1]; } } return dp[n - 1]; }}

Python

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[-1]

4、复杂度分析

• 时间复杂度：O(m×n)，需要填充整个DP表
• 空间复杂度：O(m×n)（可优化为O(n)）

Q8、最小路径和

1、题目描述

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

2、解题思路

动态规划解法

1. 状态定义：dp[i][j]表示从(0,0)到(i,j)的最小路径和
2. 转移方程 ：
   • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3. 初始条件：
   • dp[0][0] = grid[0][0]
   • 第一行只能从左方到达：dp[0][j] = dp[0][j-1] + grid[0][j]
   • 第一列只能从上方到达：dp[i][0] = dp[i-1][0] + grid[i][0]

空间优化

• 可以使用一维数组代替二维数组，空间复杂度从O(mn)降为O(n)

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int minPathSum(vector<vector>& grid) { int m = grid.size(); int n = grid[0].size(); // 创建 DP 表 vector<vector> dp(m, vector(n, 0)); // 初始化起点 dp[0][0] = grid[0][0]; // 初始化第一列 (只能从上边来) for (int i = 1; i < m; ++i) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // 初始化第一行 (只能从左边来) for (int j = 1; j < n; ++j) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // 填充 DP 表 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { // 取上方和左方的最小值加上当前格的值 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[m - 1][n - 1]; }};

// 方法2: 动态规划空间优化class Solution {public: int minPathSum(vector<vector>& grid) { int m = grid.size(); int n = grid[0].size(); // 使用一维数组优化空间 vector dp(n, 0); // 初始化起点 dp[0] = grid[0][0]; // 初始化第一行 for (int j = 1; j < n; ++j) { dp[j] = dp[j - 1] + grid[0][j]; } // 逐行计算 for (int i = 1; i < m; ++i) { // 每行的第一个元素只能从上边来 dp[0] += grid[i][0]; for (int j = 1; j < n; ++j) { // dp[j] 保存的是上一行的当前值 (上方) // dp[j-1] 保存的是当前行的前一列值 (左方) dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]; } } return dp[n - 1]; }};

Java

class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0]; // 初始化第一行 for (int j = 1; j < n; j++) { dp[j] = dp[j - 1] + grid[0][j]; } for (int i = 1; i < m; i++) { // 更新每行第一个元素 dp[0] += grid[i][0]; for (int j = 1; j < n; j++) { dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; } } return dp[n - 1]; }}

Python

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] for i in range(1, m): # 更新每行第一个元素 dp[0] += grid[i][0] for j in range(1, n): dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[-1]

4、复杂度分析

• 时间复杂度：O(mn)，需要遍历整个网格
• 空间复杂度：O(n)，使用一维数组优化后

Q9、不同路径 II

1、题目描述

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]输出：2解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

2、解题思路

动态规划解法

1. 状态定义：dp[i][j]表示到达(i,j)位置的不同路径数
2. 转移方程 ：
   • 如果当前格子是障碍物：dp[i][j] = 0
   • 否则：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 初始条件：
   • 起点(0,0)如果不是障碍物则初始为1
   • 第一行和第一列的特殊处理（只能从一个方向来）

空间优化

• 使用一维数组代替二维数组，空间复杂度从O(mn)降为O(n)

3、代码实现

C++

class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); // 创建 DP 表 vector<vector> dp(m, vector(n, 0)); // 初始化起点 dp[0][0] = (obstacleGrid[0][0] == 0) ? 1 : 0; // 初始化第一列 (只能从上边来) for (int i = 1; i < m; ++i) { if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1) { dp[i][0] = 1; } } // 初始化第一行 (只能从左边来) for (int j = 1; j < n; ++j) { if (obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1) { dp[0][j] = 1; } } // 填充 DP 表 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (obstacleGrid[i][j] == 0) {  dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }};

class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); // 使用一维数组优化空间 vector dp(n, 0); // 初始化起点 dp[0] = (obstacleGrid[0][0] == 0) ? 1 : 0; // 逐行计算 for (int i = 0; i < m; ++i) { for (int j = 0; j  0 && obstacleGrid[i][j - 1] == 0) {  dp[j] += dp[j - 1]; // 左方的路径数 } } } return dp[n - 1]; }};

class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); // 创建 DP 表, 多一行一列方便处理边界条件 vector<vector> dp(m + 1, vector(n + 1, 0)); dp[0][1] = 1; // 虚拟起点 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (obstacleGrid[i - 1][j - 1] != 1) {  dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m][n]; }};

Java

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) {  dp[j] = 0;  continue; } if (j > 0 && obstacleGrid[i][j] == 0) {  dp[j] += dp[j - 1]; } } } return dp[n - 1]; }}

Python

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [0] * n dp[0] = 1 if obstacleGrid[0][0] == 0 else 0 for i in range(m): for j in range(n): if obstacleGrid[i][j] == 1:  dp[j] = 0 elif j > 0:  dp[j] += dp[j-1] return dp[-1]

4、复杂度分析

• 时间复杂度：O(mn)，需要遍历整个网格
• 空间复杂度：O(n)（优化后）

Q10、三角形最小路径和

1、题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示：23 46 5 74 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

进阶：

• 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

2、解题思路

1. 自顶向下动态规划

• 状态定义：dp[i][j]表示从顶部到(i,j)节点的最小路径和
• 转移方程 ：
  • 第一列：dp[i][0] = dp[i-1][0] + triangle[i][0]
  • 中间元素：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
  • 对角线元素：dp[i][i] = dp[i-1][i-1] + triangle[i][i]
• 结果：min(dp[n-1][0], dp[n-1][1], …, dp[n-1][n-1])

2. 自底向上动态规划（推荐）

• 状态定义：dp[i][j]表示从(i,j)节点到底部的最小路径和
• 转移方程 ：
  • dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
• 初始条件：最后一行dp值等于三角形最后一行值
• 结果：dp[0][0]

3. 空间优化

• 使用一维数组代替二维数组，空间复杂度从O(n²)降为O(n)

3、代码实现

C++

// 方法1: 自顶向下动态规划class Solution {public: int minimumTotal(vector<vector>& triangle) { int n = triangle.size(); vector<vector> dp(n, vector(n)); // 初始化起点 dp[0][0] = triangle[0][0]; for (int i = 1; i < n; ++i) { // 处理第一列 dp[i][0] = dp[i - 1][0] + triangle[i][0]; // 处理中间元素 for (int j = 1; j < i; ++j) { dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]; } // 处理对角线元素 dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]; } // 找出最后一行的最小值 return *min_element(dp[n - 1].begin(), dp[n - 1].end()); }};

// 方法2: 自底向上动态规划class Solution {public: int minimumTotal(vector<vector>& triangle) { int n = triangle.size(); vector<vector> dp(n, vector(n)); // 初始化最后一行 for (int j = 0; j = 0; --i) { for (int j = 0; j <= i; ++j) { dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1]); } } return dp[0][0]; }};

// 方法3: 动态规划空间优化class Solution {public: int minimumTotal(vector<vector>& triangle) { int n = triangle.size(); vector dp(triangle.back()); // 初始化为最后一行 // 从倒数第二行开始向上计算 for (int i = n - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]); } } return dp[0]; }};

Java

class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[] dp = new int[n]; // 初始化最后一行 for (int j = 0; j < n; j++) { dp[j] = triangle.get(n - 1).get(j); } // 从倒数第二行开始向上计算 for (int i = n - 2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]); } } return dp[0]; }}

Python

class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: n = len(triangle) dp = triangle[-1].copy() # 从倒数第二行开始向上计算 for i in range(n-2, -1, -1): for j in range(i+1): dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) return dp[0]

4、复杂度分析

• 时间复杂度：O(n²)，需要遍历每个节点
• 空间复杂度：O(n²)（可优化为O(n)）

Q11、下降路径最小和

1、题目描述

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]输出：13解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]输出：-59解释：如图所示，为和最小的下降路径

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

2、解题思路

动态规划解法

1. 状态定义：dp[i][j]表示到达(i,j)位置的下降路径最小和
2. 转移方程：
   • 对于第一行：dp[0][j] = matrix[0][j]
   • 对于第一列：dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + matrix[i][0]
   • 对于最后一列：dp[i][n-1] = min(dp[i-1][n-1], dp[i-1][n-2]) + matrix[i][n-1]
   • 对于中间列：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
3. 初始条件：第一行的dp值等于matrix的第一行
4. 结果：最后一行中的最小值

空间优化

• 可以使用一维数组代替二维数组，空间复杂度从O(n²)降为O(n)

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int minFallingPathSum(vector<vector>& matrix) { int n = matrix.size(); vector<vector> dp(n, vector(n)); // 初始化第一行 for (int j = 0; j < n; ++j) { dp[0][j] = matrix[0][j]; } // 填充 DP 表 for (int i = 1; i < n; ++i) { // 处理第一列 dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + matrix[i][0]; // 处理中间列 for (int j = 1; j < n - 1; ++j) { dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]}) + matrix[i][j]; } // 处理最后一列 dp[i][n - 1] = min(dp[i - 1][n - 1], dp[i - 1][n - 2]) + matrix[i][n - 1]; } // 找出最后一行的最小值 return *min_element(dp[n - 1].begin(), dp[n - 1].end()); }};

// 方法2: 动态规划空间优化class Solution {public: int minFallingPathSum(vector<vector>& matrix) { int n = matrix.size(); vector dp = matrix[0]; // 初始化为第一行 for (int i = 1; i < n; ++i) { vector tmp(n); // 处理第一列 tmp[0] = min(dp[0], dp[1]) + matrix[i][0]; // 处理中间列 for (int j = 1; j < n - 1; ++j) { tmp[j] = min({dp[j - 1], dp[j], dp[j + 1]}) + matrix[i][j]; } // 处理最后一列 tmp[n - 1] = min(dp[n - 1], dp[n - 2]) + matrix[i][n - 1]; dp = move(tmp); // 更新 dp 为当前行 } return *min_element(dp.begin(), dp.end()); }};

Java

class Solution { public int minFallingPathSum(int[][] matrix) { int n = matrix.length; int[] dp = matrix[0].clone(); for (int i = 1; i < n; i++) { int[] temp = new int[n]; // 处理第一列 temp[0] = Math.min(dp[0], dp[1]) + matrix[i][0]; // 处理中间列 for (int j = 1; j < n - 1; j++) { temp[j] = Math.min(Math.min(dp[j - 1], dp[j]), dp[j + 1]) + matrix[i][j]; } // 处理最后一列 temp[n - 1] = Math.min(dp[n - 1], dp[n - 2]) + matrix[i][n - 1]; dp = temp; } int minSum = dp[0]; for (int num : dp) { minSum = Math.min(minSum, num); } return minSum; }}

Python

class Solution: def minFallingPathSum(self, matrix: List[List[int]]) -> int: n = len(matrix) dp = matrix[0].copy() for i in range(1, n): temp = [0] * n # 处理第一列 temp[0] = min(dp[0], dp[1]) + matrix[i][0] # 处理中间列 for j in range(1, n-1): temp[j] = min(dp[j-1], dp[j], dp[j+1]) + matrix[i][j] # 处理最后一列 temp[-1] = min(dp[-1], dp[-2]) + matrix[i][-1] dp = temp return min(dp)

4、复杂度分析

• 时间复杂度：O(n²)，需要遍历每个元素
• 空间复杂度：O(n²)（可优化为O(n)）

Q12、最大正方形

1、题目描述

在一个由 \'0\' 和 \'1\' 组成的二维矩阵内，找到只包含 \'1\' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]输出：4

示例 2：

输入：matrix = [[\"0\",\"1\"],[\"1\",\"0\"]]输出：1

示例 3：

输入：matrix = [[\"0\"]]输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 \'0\' 或 \'1\'

2、解题思路

1. 暴力解法（超时）

• 遍历每个’1’作为正方形的左上角
• 尝试扩展边长，检查新增的行列是否全为’1’
• 记录最大边长

2. 动态规划解法（推荐）

• 状态定义：dp[i][j]表示以(i,j)为右下角的最大正方形边长
• 转移方程：
  • 如果matrix[i][j]==‘0’：dp[i][j]=0
  • 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
• 初始条件：第一行和第一列的dp值等于matrix对应值（‘1’ 则为 1，‘0’ 则为 0）
• 结果：max(dp[i][j])²

3、代码实现

C++

// 方法1: 暴力 (超时)class Solution {public: int maximalSquare(vector<vector>& matrix) { if (matrix.empty() || matrix[0].empty()) { return 0; } int maxSide = 0; int rows = matrix.size(), cols = matrix[0].size(); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (matrix[i][j] == \'1\') {  maxSide = max(maxSide, 1); // 至少是 1 x 1 的正方形  int maxPossible = min(rows - i, cols - j);  for (int k = 1; k < maxPossible; ++k) { // 检查新增的右下角是否为 \'1\' if (matrix[i + k][j + k] == \'0\') { break; } // 检查新增的右边一列和下边一行是否全为 \'1\' bool valid = true; for (int m = 0; m < k; ++m) { if (matrix[i + k][j + m] == \'0\' || matrix[i + m][j + k] == \'0\') { valid = false; break; } } if (valid) { maxSide = max(maxSide, k + 1); } else { break; }  } } } } return maxSide * maxSide; }};

// 方法2: 动态规划class Solution {public: int maximalSquare(vector<vector>& matrix) { if (matrix.empty() || matrix[0].empty()) { return 0; } int rows = matrix.size(), cols = matrix[0].size(); vector<vector> dp(rows, vector(cols, 0)); int maxSide = 0; for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (matrix[i][j] == \'1\') {  if (i == 0 || j == 0) { dp[i][j] = 1;  } else { dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;  }  maxSide = max(maxSide, dp[i][j]); } } } return maxSide * maxSide; }};

// 方法3: 动态规划空间优化class Solution {public: int maximalSquare(vector<vector>& matrix) { if (matrix.empty() || matrix[0].empty()) { return 0; } int rows = matrix.size(), cols = matrix[0].size(); vector dp(cols, 0); int maxSide = 0, prev = 0; for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { int tmp = dp[j]; if (matrix[i][j] == \'1\') {  if (i == 0 || j == 0) { dp[j] = 1;  } else { dp[j] = min({dp[j], dp[j - 1], prev}) + 1;  }  maxSide = max(maxSide, dp[j]); } else {  dp[j] = 0; } prev = tmp; } } return maxSide * maxSide; }};

Java

class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int rows = matrix.length, cols = matrix[0].length; int[][] dp = new int[rows][cols]; int maxSide = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == \'1\') {  if (i == 0 || j == 0) { dp[i][j] = 1;  } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;  }  maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide * maxSide; }}

class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int rows = matrix.length, cols = matrix[0].length; int[] dp = new int[cols]; int maxSide = 0, prev = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { int temp = dp[j]; if (matrix[i][j] == \'1\') {  if (i == 0 || j == 0) { dp[j] = 1;  } else { dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;  }  maxSide = Math.max(maxSide, dp[j]); } else {  dp[j] = 0; } prev = temp; } } return maxSide * maxSide; }}

Python

class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) dp = [[0]*cols for _ in range(rows)] max_side = 0 for i in range(rows): for j in range(cols): if matrix[i][j] == \'1\':  if i == 0 or j == 0: dp[i][j] = 1  else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  max_side = max(max_side, dp[i][j]) return max_side * max_side

class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int:if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) dp = [0] * cols max_side = prev = 0 for i in range(rows): for j in range(cols): temp = dp[j] if matrix[i][j] == \'1\':  if i == 0 or j == 0: dp[j] = 1  else: dp[j] = min(dp[j], dp[j-1], prev) + 1  max_side = max(max_side, dp[j]) else:  dp[j] = 0 prev = temp return max_side * max_side

4、复杂度分析

• 暴力解法：
  • 时间复杂度：O(mn*min(m,n)²)
  • 空间复杂度：O(1)
• 动态规划：
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)（可优化为O(n)）

3、动态规划在字符串的应用

Q13、最长回文子串

1、题目描述

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = \"babad\"输出：\"bab\"解释：\"aba\" 同样是符合题意的答案。

示例 2：

输入：s = \"cbbd\"输出：\"bb\"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

2、解题思路

方法一：动态规划

1. 定义状态：dp[i][j]表示s[i…j]是否为回文串
2. 状态转移方程 ：
   • dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
3. 初始化：
   • 单个字符都是回文串：dp[i][i] = true
   • 两个相同字符构成回文串：dp[i][i+1] = (s[i] == s[i+1])
4. 结果：记录最长的回文子串

方法二：中心扩展算法

1. 中心思想：以每个字符为中心向两边扩展寻找回文串
2. 两种情况：
   • 奇数长度回文：以单个字符为中心
   • 偶数长度回文：以两个相同字符为中心
3. 结果：记录扩展过程中找到的最长回文串

3、代码实现

C++

// 方法1: 动态规划法class Solution {public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) { return s; } vector<vector> dp(n, vector(n, false)); int maxLen = 1, start = 0; // 单个字符都是回文 for (int i = 0; i < n; ++i) { dp[i][i] = true; } // 检查长度为 2 的字串 for (int i = 0; i < n - 1; ++i) { if (s[i] == s[i + 1]) { dp[i][i + 1] = true; start = i; maxLen = 2; } } // 检查长度大于 2 的子串 for (int len = 3; len <= n; ++len) { for (int i = 0; i  maxLen) { start = i; maxLen = len;  } } } } return s.substr(start, maxLen); }};

// 方法2: 中心扩展法class Solution {public: string longestPalindrome(string s) { if (s.empty()) { return \"\"; } int start = 0, maxLen = 1; int n = s.size(); for (int i = 0; i  maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substr(start, maxLen); }private: int expandAroundCenter(const string& s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { left--; right++; } return right - left - 1; // 计算回文长度 }};

Java

class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) { return \"\"; } int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }}

Python

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] max_len = 1 start = 0 # 单个字符都是回文 for i in range(n): dp[i][i] = True # 检查长度为2的子串 for i in range(n - 1): if s[i] == s[i + 1]: dp[i][i + 1] = True start = i max_len = 2 # 检查长度大于2的子串 for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and dp[i + 1][j - 1]:  dp[i][j] = True  if length > max_len: start = i max_len = length return s[start:start + max_len]

4、复杂度分析

• 动态规划：时间复杂度O(n²)，空间复杂度O(n²)
• 中心扩展：时间复杂度O(n²)，空间复杂度O(1)

Q14、单词拆分

1、题目描述

给你一个字符串 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 中的所有字符串 互不相同

2、解题思路

动态规划方法

1. 定义状态：dp[i]表示字符串s的前i个字符能否被拆分成字典中的单词

2. 状态转移方程 ：

   • dp[i] = true 如果存在j < i，使得dp[j]为true且s[j…i-1]在字典中

3. 初始化 ：

   • dp[0] = true（空字符串默认可以被拆分）

4. 优化 ：

   • 使用哈希集合存储字典以便快速查找
   • 反向遍历可以减少不必要的检查

3、代码实现

C++

class Solution {public: bool wordBreak(string s, vector& wordDict) { unordered_set dict(wordDict.begin(), wordDict.end()); // 将字典存入哈希集合 int n = s.length(); vector dp(n + 1, false); // dp 数组, dp[i] 表示前 i 个字符是否被拆分 dp[0] = true;  // 空字符串可以被拆分 // 遍历每个字符位置 for (int i = 1; i <= n; ++i) { // 检查所有可能的分割点 for (int j = 0; j < i; ++j) { // 如果前 j 个可拆分且 j 到 i 在字典中 if (dp[j] && dict.count(s.substr(j, i - j))) {  dp[i] = true;  break; // 找到一个有效分割即可 } } } return dp[n]; // 返回整个字符串能否被拆分 }};

Java

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); // 字典存入哈希集合 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++) { if (dp[j] && dict.contains(s.substring(j, i))) {  dp[i] = true;  break; } } } return dp[n]; }}

Python

word_set = set(wordDict) # 转换为集合提高查找效率 n = len(s) dp = [False] * (n + 1) dp[0] = True # 空字符串 for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set:  dp[i] = True  break return dp[n]

4、复杂度分析

• 时间复杂度：O(n²)，其中n是字符串长度
• 空间复杂度：O(n)，用于存储dp数组

Q15、最长回文子序列

1、题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = \"bbbab\"输出：4解释：一个可能的最长回文子序列为 \"bbbb\" 。

示例 2：

输入：s = \"cbbd\"输出：2解释：一个可能的最长回文子序列为 \"bb\" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

2、解题思路

动态规划解法

• 状态定义：dp[i][j]表示字符串s[i…j]的最长回文子序列长度
• 转移方程：
  • 如果 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2
  • 否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
• 初始条件：dp[i][i] = 1（单个字符的回文长度为1）
• 计算顺序：从字符串末尾开始倒序计算，或从对角线开始向右上角填充
• 结果：dp[0][n-1]（整个字符串的最长回文子序列长度）

3、代码实现

C++

// 方法1: 从对角线开始填充class Solution {public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector> dp(n, vector(n, 0)); // 每个单字符都是长度为 1 的回文 for (int i = 0; i < n; ++i) { dp[i][i] = 1; } // 从对角线开始向右上方填充 DP 表 for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (s[i] == s[j]) {  dp[i][j] = dp[i + 1][j - 1] + 2; } else {  dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }};

// 方法2: 从右下角开始倒序计算class Solution {public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector> dp(n, vector(n, 0)); // 从右下角开始倒序计算 for (int i = n - 1; i >= 0; --i) { dp[i][i] = 1; // 单个字符 for (int j = i + 1; j < n; ++j) { if (s[i] == s[j]) {  dp[i][j] = dp[i + 1][j - 1] + 2; } else {  dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }};

// 方法3: 动态规划空间优化class Solution {public: int longestPalindromeSubseq(string s) { int n = s.size(); vector dp(n, 0), prev(n, 0); for (int i = n - 1; i >= 0; --i) { dp[i] = 1; // 单个字符 for (int j = i + 1; j < n; ++j) { if (s[i] == s[j]) {  dp[j] = prev[j - 1] + 2; } else {  dp[j] = max(prev[j], dp[j - 1]); } } prev = dp; } return dp[n - 1]; }};

Java

class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; // 单个字符 for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) {  dp[i][j] = dp[i + 1][j - 1] + 2; } else {  dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }}

class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[] dp = new int[n]; for (int i = n - 1; i >= 0; i--) { dp[i] = 1; // 单个字符 int prev = 0; for (int j = i + 1; j < n; j++) { int temp = dp[j]; if (s.charAt(i) == s.charAt(j)) {  dp[j] = prev + 2; } else {  dp[j] = Math.max(dp[j], dp[j - 1]); } prev = temp; } } return dp[n - 1]; }}

Python

class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n-1, -1, -1): dp[i][i] = 1 # 单个字符 for j in range(i+1, n): if s[i] == s[j]:  dp[i][j] = dp[i+1][j-1] + 2 else:  dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][n-1]

class Solution: def longestPalindromeSubseq(self, s: str) -> int:n = len(s) dp = [0] * n prev_dp = [0] * n for i in range(n-1, -1, -1): dp[i] = 1 # 单个字符 for j in range(i+1, n): if s[i] == s[j]:  dp[j] = prev_dp[j-1] + 2 else:  dp[j] = max(prev_dp[j], dp[j-1]) prev_dp = dp.copy() return dp[-1]

4、复杂度分析

• 时间复杂度：O(n²)，需要填充 n×n 的 DP 表
• 空间复杂度：O(n²)（可优化为 O(n)）

Q16、编辑距离

1、题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = \"horse\", word2 = \"ros\"输出：3解释：horse -> rorse (将 \'h\' 替换为 \'r\')rorse -> rose (删除 \'r\')rose -> ros (删除 \'e\')

示例 2：

输入：word1 = \"intention\", word2 = \"execution\"输出：5解释：intention -> inention (删除 \'t\')inention -> enention (将 \'i\' 替换为 \'e\')enention -> exention (将 \'n\' 替换为 \'x\')exention -> exection (将 \'n\' 替换为 \'c\')exection -> execution (插入 \'u\')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

2、解题思路

动态规划方法

1. 定义状态：dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符所需的最小操作数
2. 状态转移方程 ：
   • 当 word1[i-1] == word2[j-1] 时：dp[i][j] = dp[i-1][j-1]（无需操作）
   • 否则：dp[i][j] = min(
     dp[i][j-1] + 1, // 插入
     dp[i-1][j] + 1, // 删除
     dp[i-1][j-1] + 1 // 替换
     )
3. 初始化 ：
   • dp[i][0] = i（删除所有字符）
   • dp[0][j] = j（插入所有字符）
4. 结果：dp[m][n]（m和n分别为word1和word2的长度）

3、代码实现

C++

// 方法1: 动态规划 二维数组class Solution {public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); // 初始化: 空字符串转换 操作2: 删除一个字符 for (int i = 0; i <= m; ++i) { dp[i][0] = i; } for (int j = 0; j <= n; ++j) { dp[0][j] = j; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1]; } else {  dp[i][j] = 1 + min({  dp[i][j - 1], // 插入  dp[i - 1][j], // 删除  dp[i - 1][j - 1] // 替换 }); } } } return dp[m][n]; }};

// 方法2: 动态规划 一维数组class Solution {public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector prev(n + 1), curr(n + 1); // 初始化第一行 for (int j = 0; j <= n; ++j) { prev[j] = j; } for (int i = 1; i <= m; ++i) { curr[0] = i; // 初始化第一列 for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) {  curr[j] = prev[j - 1]; } else {  curr[j] = 1 + min({ prev[j], // 删除 curr[j - 1], // 插入 prev[j - 1] // 替换 }); } } swap(prev, curr); } return prev[n]; }};

Java

class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m + 1][n + 1]; // 初始化 for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][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], // 删除 Math.min(  dp[i][j - 1], // 插入  dp[i - 1][j - 1] // 替换 )); } } } return dp[m][n]; }}

Python

class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) prev = [j for j in range(n + 1)] for i in range(1, m + 1): curr = [0] * (n + 1) curr[0] = i for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]:  curr[j] = prev[j - 1] else:  curr[j] = 1 + min( prev[j], # 删除 curr[j - 1], # 插入 prev[j - 1] # 替换  ) prev = curr return prev[n]

4、复杂度分析

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)（可优化为O(min(m,n))）

Q17、两个字符串的最小ASCII删除和

1、题目描述

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = \"sea\", s2 = \"eat\"输出: 231解释: 在 \"sea\" 中删除 \"s\" 并将 \"s\" 的值(115)加入总和。在 \"eat\" 中删除 \"t\" 并将 116 加入总和。结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = \"delete\", s2 = \"leet\"输出: 403解释: 在 \"delete\" 中删除 \"dee\" 字符串变成 \"let\"，将 100[d]+101[e]+101[e] 加入总和。在 \"leet\" 中删除 \"e\" 将 101[e] 加入总和。结束时，两个字符串都等于 \"let\"，结果即为 100+101+101+101 = 403 。如果改为将两个字符串转换为 \"lee\" 或 \"eet\"，我们会得到 433 或 417 的结果，比答案更大。

提示:

• 0 <= s1.length, s2.length <= 1000
• s1 和 s2 由小写英文字母组成

2、解题思路

方法一：最长公共子序列(LCS)变种

1. 计算最长公共子序列的ASCII和：找到s1和s2中ASCII和最大的公共子序列
2. 计算总ASCII和：s1和s2所有字符的ASCII总和
3. 结果计算：总ASCII和减去两倍的LCS ASCII和

方法二：直接动态规划

1. 状态定义：dp[i][j]表示使s1前i个字符和s2前j个字符相等所需删除的最小ASCII和

2. 转移方程 ：

   • 如果s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1]
   • 否则：dp[i][j] = min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1])

3. 初始条件：

   • dp[i][0] = dp[i-1][0] + s1[i-1]（删除s1前i个字符的和）
   • dp[0][j] = dp[0][j-1] + s2[j-1]（删除s2前j个字符的和）

3、代码实现

C++

// 方法1: LCS变种class Solution {public: int minimumDeleteSum(string s1, string s2) { int m = s1.size(), n = s2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); // 计算最长公共子序列的 ASCII 和 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s1[i - 1] == s2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1] + s1[i - 1]; } else {  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } // 计算总 ASCII 和 int total = 0; for (char c : s1) { total += c; } for (char c : s2) { total += c; } return total - 2 * dp[m][n]; }};

// 方法2: 动态规划class Solution {public: int minimumDeleteSum(string s1, string s2) { int m = s1.size(), n = s2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); // 初始化边界条件 for (int i = 1; i <= m; ++i) { dp[i][0] = dp[i - 1][0] + s1[i - 1]; } for (int j = 1; j <= n; ++j) { dp[0][j] = dp[0][j - 1] + s2[j - 1]; } // 填充 DP 表 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s1[i - 1] == s2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1]; } else {  dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]); } } } return dp[m][n]; }};

// 方法3: 动态规划空间优化class Solution {public: int minimumDeleteSum(string s1, string s2) { int m = s1.size(), n = s2.size(); vector dp(n + 1, 0); // 初始化 s2 的删除成本 for (int j = 1; j <= n; ++j) { dp[j] = dp[j - 1] + s2[j - 1]; } for (int i = 1; i <= m; ++i) { int pre = dp[0]; // 保存左上角的值 dp[0] += s1[i - 1]; // 更新 s1 的删除成本 for (int j = 1; j <= n; ++j) { int tmp = dp[j]; if (s1[i - 1] == s2[j - 1]) {  dp[j] = pre; } else {  dp[j] = min(dp[j] + s1[i - 1], dp[j - 1] + s2[j - 1]); } pre = tmp; } } return dp[n]; }};

Java

class Solution { public int minimumDeleteSum(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; // 初始化边界条件 for (int i = 1; i <= m; i++) { dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); } for (int j = 1; j <= n; j++) { dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); } // 填充DP表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) {  dp[i][j] = dp[i - 1][j - 1]; } else {  dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1)); } } } return dp[m][n]; }}

class Solution { public int minimumDeleteSum(String s1, String s2) { int m = s1.length(), n = s2.length(); int[] dp = new int[n + 1]; // 初始化s2的删除成本 for (int j = 1; j <= n; j++) { dp[j] = dp[j - 1] + s2.charAt(j - 1); } for (int i = 1; i <= m; i++) { int pre = dp[0]; dp[0] += s1.charAt(i - 1); for (int j = 1; j <= n; j++) { int temp = dp[j]; if (s1.charAt(i - 1) == s2.charAt(j - 1)) {  dp[j] = pre; } else {  dp[j] = Math.min(dp[j] + s1.charAt(i - 1), dp[j - 1] + s2.charAt(j - 1)); } pre = temp; } } return dp[n]; }}

Python

class Solution: def minimumDeleteSum(self, s1: str, s2: str) -> int: m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(1, m + 1): dp[i][0] = dp[i-1][0] + ord(s1[i-1]) for j in range(1, n + 1): dp[0][j] = dp[0][j-1] + ord(s2[j-1]) # 填充DP表 for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]:  dp[i][j] = dp[i-1][j-1] else:  dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])) return dp[m][n]

class Solution: def minimumDeleteSum(self, s1: str, s2: str) -> int: m, n = len(s1), len(s2) dp = [0] * (n + 1) # 初始化s2的删除成本 for j in range(1, n + 1): dp[j] = dp[j-1] + ord(s2[j-1]) for i in range(1, m + 1): pre = dp[0] dp[0] += ord(s1[i-1]) for j in range(1, n + 1): temp = dp[j] if s1[i-1] == s2[j-1]:  dp[j] = pre else:  dp[j] = min(dp[j] + ord(s1[i-1]), dp[j-1] + ord(s2[j-1])) pre = temp return dp[n]

4、复杂度分析

• 时间复杂度：O(mn)，m和n分别为s1和s2的长度
• 空间复杂度：O(mn)（可优化为O(min(m,n))）

Q18、不同的子序列

1、题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 1：

输入：s = \"rabbbit\", t = \"rabbit\"输出：3解释：如下所示, 有 3 种可以从 s 中得到 \"rabbit\" 的方案。rabbbitrabbbitrabbbit

示例 2：

输入：s = \"babgbag\", t = \"bag\"输出：5解释：如下所示, 有 5 种可以从 s 中得到 \"bag\" 的方案。 babgbagbabgbagbabgbagbabgbagbabgbag

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

2、解题思路

动态规划解法

• 状态定义：dp[i][j]表示s的前i个字符中t的前j个字符出现的子序列个数
• 转移方程：
  • 如果s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    • dp[i-1][j-1]：匹配当前字符
    • dp[i-1][j]：不匹配当前字符
  • 否则：dp[i][j] = dp[i-1][j]
• 初始条件：
  • dp[i][0] = 1（空字符串是任何字符串的子序列）
  • dp[0][j] = 0（j>0，空字符串无法包含非空字符串）
• 结果：dp[m][n]，其中m是s的长度，n是t的长度

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int numDistinct(string s, string t) { int m = s.size(), n = t.size(); if (m < n) { return 0; } vector<vector> dp( m + 1, vector(n + 1, 0)); // 初始化: 空字符串是任何字符串的子序列 for (int i = 0; i <= m; ++i) { dp[i][0] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s[i - 1] == t[j - 1]) {  dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } else {  dp[i][j] = dp[i - 1][j]; } } } return dp[m][n]; }};

// 方法2: 动态规划优化class Solution {public: int numDistinct(string s, string t) { int m = s.size(), n = t.size(); if (m < n) { return 0; } vector dp(n + 1, 0); dp[0] = 1; // 空字符串匹配 for (int i = 1; i = 1; --j) { if (s[i - 1] == t[j - 1]) {  dp[j] += dp[j - 1]; } } } return dp[n]; }};

Java

class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); if (m < n) return 0; int[][] dp = new int[m + 1][n + 1]; // 初始化 for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) {  dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } else {  dp[i][j] = dp[i - 1][j]; } } } return dp[m][n]; }}

class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); if (m < n) return 0; int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= m; i++) { // 从后往前更新 for (int j = n; j >= 1; j--) { if (s.charAt(i - 1) == t.charAt(j - 1)) {  dp[j] += dp[j - 1]; } } } return dp[n]; }}

Python

class Solution: def numDistinct(self, s: str, t: str) -> int: m, n = len(s), len(t) if m < n: return 0 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化 for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i-1] == t[j-1]:  dp[i][j] = dp[i-1][j-1] + dp[i-1][j] else:  dp[i][j] = dp[i-1][j] return dp[m][n]

class Solution: def numDistinct(self, s: str, t: str) -> int: m, n = len(s), len(t) if m < n: return 0 dp = [0] * (n + 1) dp[0] = 1 for i in range(1, m + 1): # 从后往前更新 for j in range(n, 0, -1): if s[i-1] == t[j-1]:  dp[j] += dp[j-1] return dp[n]

4、复杂度分析

• 时间复杂度：O(mn)，m和n分别为s和t的长度
• 空间复杂度：O(mn)（可优化为O(n)）

4、最长递增子序列

Q19、最长递增子序列

1、题目描述

给你一个整数数组 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
• -104 <= nums[i] <= 104

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2、解题思路

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

1. 定义状态：dp[i]表示以nums[i]结尾的最长递增子序列长度
2. 状态转移 ：
   • 对于每个i，遍历所有j < i
   • 如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)
3. 初始化：所有dp[i]初始化为1
4. 结果：dp数组中的最大值

方法二：动态规划+二分查找（O(n log n)）

1. 维护数组：dp数组存储当前可能的最长递增子序列
2. 遍历元素 ：
   • 当前元素大于dp末尾元素：直接追加
   • 否则：用二分查找找到第一个不小于当前元素的位置并替换
3. 结果：dp数组的长度即为答案

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int lengthOfLIS(vector& nums) { int n = nums.size(); vector dp(n, 1); // dp[i] 表示以 nums[i] 结尾的 LIS 长度 int max_len = 1; // 至少为 1 for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) {  dp[i] = max(dp[i], dp[j] + 1); } } max_len = max(max_len, dp[i]); } return max_len; }};

// 方法2: 贪心 + 二分查找class Solution {public: int lengthOfLIS(vector& nums) { vector dp; // 维护的可能 LIS 序列 for (int num : nums) { // 查找第一个不小于 num 的位置 auto it = lower_bound(dp.begin(), dp.end(), num); if (it == dp.end()) { dp.push_back(num); // num 比所有都大, 直接追加 } else { *it = num; // 替换第一个不小于 num 的元素 } } return dp.size(); }};

Java

class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 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); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }}

class Solution { public int lengthOfLIS(int[] nums) { List<Integer> dp = new ArrayList<>(); for (int num : nums) { int pos = binarySearch(dp, num); if (pos == dp.size()) { dp.add(num); } else { dp.set(pos, num); } } return dp.size(); } private int binarySearch(List<Integer> list, int target) { int left = 0, right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) < target) { left = mid + 1; } else { right = mid; } } return left; }}

Python

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = [1] * n max_len = 1 for i in range(1, n): for j in range(i): if nums[j] < nums[i]:  dp[i] = max(dp[i], dp[j] + 1) max_len = max(max_len, dp[i]) return max_len

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [] for num in nums: idx = bisect.bisect_left(dp, num) if idx == len(dp): dp.append(num) else: dp[idx] = num return len(dp)

4、复杂度分析

• 方法一：时间复杂度O(n²)，空间复杂度O(n)
• 方法二：时间复杂度O(n log n)，空间复杂度O(n)

Q20、最长递增子序列的个数

1、题目描述

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]输出: 2解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]输出: 5解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示:

• 1 <= nums.length <= 2000
• -106 <= nums[i] <= 106

2、解题思路

动态规划解法

1. 定义状态：

   • len[i]：以nums[i]结尾的最长递增子序列的长度
   • count[i]：以nums[i]结尾的最长递增子序列的个数

2. 状态转移 ：

   • 对于每个i，遍历所有j < i
   • 如果nums[j] < nums[i]：
     • 如果len[j] + 1 == len[i]：说明找到了相同长度的新路径，count[i] += count[j]
     • 如果len[j] + 1 > len[i]：发现更长的子序列，更新len[i]和count[i]

3. 跟踪最大值：

   • 维护全局最大长度retlen和对应数量retcount
   • 遍历过程中更新这两个值

3、代码实现

C++

class Solution {public: int findNumberOfLIS(vector& nums) { int n = nums.size(); if (n == 0) { return 0; } vector len(n, 1); // len[i] 表示以 nums[i] 结尾的 LIS 长度 vector count(n, 1); // count[i] 表示以 nums[i] 结尾的 LIS 个数 int max_len = 1; // 全局最大长度 int result = 0; // 最终结果 for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j]  len[i]) { // 发现更长的子序列, 更新长度和计数 len[i] = len[j] + 1; count[i] = count[j];  } else if (len[j] + 1 == len[i]) { // 发现相同长度的新路径, 增加计数 count[i] += count[j];  } } } // 更新全局最大值 if (len[i] > max_len) { max_len = len[i]; result = count[i]; } else if (len[i] == max_len) { result += count[i]; } } return result; }};

Java

class Solution { public int findNumberOfLIS(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int[] len = new int[n]; // len[i]表示以nums[i]结尾的LIS长度 int[] count = new int[n]; // count[i]表示以nums[i]结尾的LIS个数 Arrays.fill(len, 1); Arrays.fill(count, 1); int maxLen = 1; // 全局最大长度 int result = 0; // 最终结果 for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) {  if (len[j] + 1 > len[i]) { // 发现更长的子序列，更新长度和计数 len[i] = len[j] + 1; count[i] = count[j];  } else if (len[j] + 1 == len[i]) { // 发现相同长度的新路径，增加计数 count[i] += count[j];  } } } // 更新全局最大值 if (len[i] > maxLen) { maxLen = len[i]; result = count[i]; } else if (len[i] == maxLen) { result += count[i]; } } return result; }}

Python

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 length = [1] * n # length[i]表示以nums[i]结尾的LIS长度 count = [1] * n # count[i]表示以nums[i]结尾的LIS个数 max_len = 1 # 全局最大长度 result = 0 # 最终结果 for i in range(n): for j in range(i): if nums[j] < nums[i]:  if length[j] + 1 > length[i]: # 发现更长的子序列，更新长度和计数 length[i] = length[j] + 1 count[i] = count[j]  elif length[j] + 1 == length[i]: # 发现相同长度的新路径，增加计数 count[i] += count[j] # 更新全局最大值 if length[i] > max_len: max_len = length[i] result = count[i] elif length[i] == max_len: result += count[i] return result

4、复杂度分析

• 时间复杂度：O(n²)，双重循环遍历
• 空间复杂度：O(n)，需要两个长度为n的数组

Q21、最长数对链

1、题目描述

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]输出：2解释：最长的数对链是 [1,2] -> [3,4] 。

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]输出：3解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

2、解题思路

方法一：动态规划

1. 排序：先按数对的第一个元素升序排序
2. DP数组：dp[i] 表示以第 i 个数对结尾的最长链长度
3. 状态转移 ：
   • 对于每个数对 i，检查所有 j < i 的数对
   • 如果pairs[j][1] < pairs[i][0]，则可以形成链，dp[i] = max(dp[i], dp[j]+1)
4. 结果：dp 数组中的最大值

方法二：贪心算法

1. 排序：按数对的第二个元素升序排序
2. 贪心选择 ：
   • 维护当前链的最后一个数对的右边界值
   • 遍历排序后的数对，选择第一个可以加入链的数对（左边界大于当前右边界）
3. 结果：链的长度

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int findLongestChain(vector<vector>& pairs) { // 按数对的第一个元素升序排序 sort(pairs.begin(), pairs.end()); int n = pairs.size(); vector dp(n, 1); // 每个数对本身长度为 1 的链 for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { // 如果 j 可以接在 i 前面 if (pairs[j][1] < pairs[i][0]) {  dp[i] = max(dp[i], dp[j] + 1); } } } // 返回 dp 数组中的最大值 return *max_element(dp.begin(), dp.end()); }};

// 方法2: 贪心算法class Solution {public: int findLongestChain(vector<vector>& pairs) { // 按数对的第二个元素升序排序 sort(pairs.begin(), pairs.end(), [](const vector& a, const vector& b) {  return a[1] < b[1]; }); int curr = INT_MIN; // 当前链最后一个数对的右边界 int ret = 0; // 链的长度 for (const auto& p : pairs) { // 如果当前数对的左边界大于当前右边界, 可以加入链 if (curr < p[0]) { curr = p[1]; ++ret; } } return ret; }};

Java

// 方法1: 动态规划class Solution { public int findLongestChain(int[][] pairs) { // 按数对的第一个元素升序排序 Arrays.sort(pairs, (a, b) -> a[0] - b[0]); int n = pairs.length; int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (pairs[j][1] < pairs[i][0]) {  dp[i] = Math.max(dp[i], dp[j] + 1); } } } // 返回dp数组中的最大值 return Arrays.stream(dp).max().getAsInt(); }}

// 方法2: 贪心算法class Solution { public int findLongestChain(int[][] pairs) { // 按数对的第二个元素升序排序 Arrays.sort(pairs, (a, b) -> a[1] - b[1]); int curr = Integer.MIN_VALUE; int ret = 0; for (int[] p : pairs) { if (curr < p[0]) { curr = p[1]; ret++; } } return ret; }}

Python

class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: # 按数对的第一个元素升序排序 pairs.sort() n = len(pairs) dp = [1] * n for i in range(1, n): for j in range(i): if pairs[j][1] < pairs[i][0]:  dp[i] = max(dp[i], dp[j] + 1) return max(dp)

class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: # 按数对的第二个元素升序排序 pairs.sort(key=lambda x: x[1]) curr = float(\'-inf\') ret = 0 for p in pairs: if curr < p[0]: curr = p[1] ret += 1 return ret

4、复杂度分析

• 动态规划：

  • 时间：O(n²)（排序O(n log n) + 双重循环O(n²)）
  • 空间：O(n)（DP数组）

• 贪心算法：

  • 时间：O(n log n)（排序）
  • 空间：O(1)（常数空间）

Q22、最长定差子序列

1、题目描述

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1输出：4解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1输出：1解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2输出：4解释：最长的等差子序列是 [7,5,3,1]。

提示：

• 1 <= arr.length <= 105
• -104 <= arr[i], difference <= 104

2、解题思路

动态规划 + 哈希表

1. 状态定义：使用哈希表dp记录以每个数字结尾的最长等差子序列长度
2. 状态转移 ：
   • 对于当前数字arr[i]，查找arr[i] - difference是否存在于哈希表中
   • 如果存在，则dp[arr[i]] = dp[arr[i]-difference] + 1
   • 否则，dp[arr[i]] = 1
3. 更新最大值：在遍历过程中维护全局最大值

3、代码实现

C++

class Solution {public: int longestSubsequence(vector& arr, int difference) { unordered_map dp; // key: 数字, value: 以该数字结尾的最长子序列长度 int max_len = 0; for (int num : arr) { // 查找前一个可能的数字 int prev = num - difference; // 更新当前数字的最长子序列长度 dp[num] = dp.count(prev) ? dp[prev] + 1 : 1; // 更新全局最大值 max_len = max(max_len, dp[num]); } return max_len; }};

Java

class Solution { public int longestSubsequence(int[] arr, int difference) { HashMap<Integer, Integer> dp = new HashMap<>(); int maxLen = 0; for (int num : arr) { int prev = num - difference; dp.put(num, dp.getOrDefault(prev, 0) + 1); maxLen = Math.max(maxLen, dp.get(num)); } return maxLen; }}

Python

class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: dp = {} max_len = 0 for num in arr: prev = num - difference dp[num] = dp.get(prev, 0) + 1 max_len = max(max_len, dp[num]) return max_len

4、复杂度分析

• 时间复杂度：O(n)，只需一次遍历数组
• 空间复杂度：O(n)，哈希表存储每个数字的状态

Q23、最长等差数列

1、题目描述

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]输出：4解释： 整个数组是公差为 3 的等差数列。

示例 2：

输入：nums = [9,4,7,2,10]输出：3解释：最长的等差子序列是 [4,7,10]。

示例 3：

输入：nums = [20,1,15,3,10,5,8]输出：4解释：最长的等差子序列是 [20,15,10,5]。

提示：

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

2、解题思路

动态规划 + 哈希表

1. 状态定义：dp[i][j]表示以nums[i]和nums[j]作为最后两个元素的最长等差子序列长度
2. 状态转移 ：
   • 对于每个j>i，计算可能的前一个元素a = 2*nums[i]-nums[j]
   • 如果a存在于数组中，则dp[i][j] = dp[hash[a]][i] + 1
3. 哈希表优化：使用哈希表记录每个数字的最新位置，便于快速查找
4. 初始化：所有可能的数对初始长度为2
5. 维护最大值：在遍历过程中维护全局最大值

3、代码实现

C++

class Solution {public: int longestArithSeqLength(vector& nums) { int n = nums.size(); if (n <= 2) { return n; // 数组长度 <= 2 时直接返回 } unordered_map pos;  // 记录数字到索引的映射 vector<vector> dp(n, vector(n, 2)); // dp[i][j] 初始为 2 int max_len = 2; // 至少为 2 for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { // 计算可能的前一个元素 int a = 2 * nums[i] - nums[j]; // 如果 a 存在且位置在 i 之前 if (pos.count(a) && pos[a] < i) {  dp[i][j] = dp[pos[a]][i] + 1;  max_len = max(max_len, dp[i][j]); } } // 记录当前数字的位置 pos[nums[i]] = i; } return max_len; }};

Java

class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; if (n <= 2) { return n; } HashMap<Integer, Integer> pos = new HashMap<>(); int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = 2; // 初始化为2 } } int maxLen = 2; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int a = 2 * nums[i] - nums[j]; if (pos.containsKey(a) && pos.get(a) < i) {  dp[i][j] = dp[pos.get(a)][i] + 1;  maxLen = Math.max(maxLen, dp[i][j]); } } pos.put(nums[i], i); } return maxLen; }}

Python

class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: n = len(nums) if n <= 2: return n pos = {} dp = [[2] * n for _ in range(n)] max_len = 2 for i in range(n): for j in range(i + 1, n): a = 2 * nums[i] - nums[j] if a in pos and pos[a] < i:  dp[i][j] = dp[pos[a]][i] + 1  max_len = max(max_len, dp[i][j]) pos[nums[i]] = i return max_len

4、复杂度分析

• 时间复杂度：O(n²)，双重循环遍历所有数对
• 空间复杂度：O(n²)，用于存储dp数组

Q24、俄罗斯套娃信封问题

1、题目描述

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]输出：3解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]输出：1

提示：

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

2、解题思路

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

1. 排序：按宽度升序排序，宽度相同时按高度降序排序
2. DP数组：f[i]表示以第 i 个信封为最外层信封时的最大套娃数
3. 状态转移 ：
   • 对于每个信封 i，检查所有 j < i 的信封
   • 如果envelopes[j][1] < envelopes[i][1]，则f[i] = max(f[i], f[j] + 1)
4. 结果：取DP数组中的最大值

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

1. 排序：同方法一
2. 维护序列 ：使用数组f维护可能的最长递增子序列
   • 如果当前信封高度大于f最后一个元素，直接加入
   • 否则，用二分查找找到第一个≥当前高度的位置并替换

3、代码实现

C++

// 方法1: 动态规划 超时！！class Solution {public: int maxEnvelopes(vector<vector>& envelopes) { if (envelopes.empty()) { return 0; } // 按宽度升序, 高度降序排序 sort(envelopes.begin(), envelopes.end(), [](const vector& a, const vector& b) {  return a[0]  b[1]); }); int n = envelopes.size(); vector dp(n, 1); // 每个信封自身长度为 1 int max_len = 1; for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { // 只需要比较高度 (宽度已保证可以套入) if (envelopes[j][1] < envelopes[i][1]) {  dp[i] = max(dp[i], dp[j] + 1); } } max_len = max(max_len, dp[i]); } return max_len; }};

// 方法2: 贪心 + 二分查找class Solution {public: int maxEnvelopes(vector<vector>& envelopes) { if (envelopes.empty()) { return 0; } // 按宽度升序, 高度降序 sort(envelopes.begin(), envelopes.end(), [](const vector& a, const vector& b) {  return a[0]  b[1]); }); vector seq; // 维护可能的最长递增子序列 seq.push_back(envelopes[0][1]); for (int i = 1; i  seq.back()) { seq.push_back(h); } else { // 二分查找第一个 >= h 的位置 auto it = lower_bound(seq.begin(), seq.end(), h); *it = h; } } return seq.size(); }};

Java

class Solution { public int maxEnvelopes(int[][] envelopes) { if (envelopes.length == 0) { return 0; } // 按宽度升序，高度降序排序 Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]); List<Integer> seq = new ArrayList<>(); seq.add(envelopes[0][1]); for (int i = 1; i < envelopes.length; i++) { int h = envelopes[i][1]; if (h > seq.get(seq.size() - 1)) { seq.add(h); } else { // 二分查找第一个≥h的位置 int idx = binarySearch(seq, h); seq.set(idx, h); } } return seq.size(); } private int binarySearch(List<Integer> list, int target) { int left = 0, right = list.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) < target) { left = mid + 1; } else { right = mid; } } return left; }}

Python

class Solution: def maxEnvelopes(self, envelopes: List[List[int]]) -> int: if not envelopes: return 0 # 按宽度升序，高度降序排序 envelopes.sort(key=lambda x: (x[0], -x[1])) seq = [] for _, h in envelopes: idx = bisect.bisect_left(seq, h) if idx == len(seq): seq.append(h) else: seq[idx] = h return len(seq)

4、复杂度分析

• 动态规划：
  • 时间：O(n²)（排序O(n log n) + 双重循环O(n²)）
  • 空间：O(n)（DP数组）
• 贪心+二分：
  • 时间：O(n log n)（排序O(n log n) + 遍历+二分O(n log n)）
  • 空间：O(n)（维护序列）

Q25、找出到每个位置为止最长的有效障碍赛跑路线

1、题目描述

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

• 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
• 在这条路线中，必须包含第 i 个障碍。
• 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
• 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。

返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

示例 1：

输入：obstacles = [1,2,3,2]输出：[1,2,3,3]解释：每个位置的最长有效障碍路线是：- i = 0: [1], [1] 长度为 1- i = 1: [1,2], [1,2] 长度为 2- i = 2: [1,2,3], [1,2,3] 长度为 3- i = 3: [1,2,3,2], [1,2,2] 长度为 3

示例 2：

输入：obstacles = [2,2,1]输出：[1,2,1]解释：每个位置的最长有效障碍路线是：- i = 0: [2], [2] 长度为 1- i = 1: [2,2], [2,2] 长度为 2- i = 2: [2,2,1], [1] 长度为 1

示例 3：

输入：obstacles = [3,1,5,6,4,2]输出：[1,1,2,3,2,2]解释：每个位置的最长有效障碍路线是：- i = 0: [3], [3] 长度为 1- i = 1: [3,1], [1] 长度为 1- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2

提示：

• n == obstacles.length
• 1 <= n <= 105
• 1 <= obstacles[i] <= 107

2、解题思路

贪心+二分查找法

1. 维护序列：使用数组d来维护可能的最长非递减子序列
2. 遍历处理 ：
   • 如果当前障碍大于等于d最后一个元素，直接加入d，结果即为当前d的长度
   • 否则，使用二分查找找到第一个大于当前障碍的位置并替换，结果为该位置+1
3. 结果构建：将每个位置的结果存入ret数组并返回

3、代码实现

C++

class Solution {public: vector longestObstacleCourseAtEachPosition(vector& obstacles) { vector d; // 维护的可能最长非递减子序列 vector ret; // 结果数组 for (int ob : obstacles) { if (d.empty() || ob >= d.back()) { // 当前障碍可以直接加入序列 d.push_back(ob); ret.push_back(d.size()); } else { // 找到第一个大于 ob 的位置 auto it = upper_bound(d.begin(), d.end(), ob); int pos = it - d.begin(); // 替换该位置的值 d[pos] = ob; // 结果为位置 +1 (因为序列从 0 开始) ret.push_back(pos + 1); } } return ret; }};

Java

class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { List<Integer> d = new ArrayList<>(); // 维护的可能最长非递减子序列 int[] ret = new int[obstacles.length]; // 结果数组 for (int i = 0; i < obstacles.length; i++) { int ob = obstacles[i]; if (d.isEmpty() || ob >= d.get(d.size() - 1)) { // 当前障碍可以直接加入序列 d.add(ob); ret[i] = d.size(); } else { // 二分查找第一个大于ob的位置 int pos = binarySearch(d, ob); // 替换该位置的值 d.set(pos, ob); // 结果为位置+1（因为序列从0开始） ret[i] = pos + 1; } } return ret; } // 二分查找第一个大于target的元素位置 private int binarySearch(List<Integer> list, int target) { int left = 0, right = list.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (list.get(mid) <= target) { left = mid + 1; } else { right = mid - 1; } } return left; }}

Python

class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]: d = [] # 维护的可能最长非递减子序列 ret = [] # 结果数组 for ob in obstacles: if not d or ob >= d[-1]: # 当前障碍可以直接加入序列 d.append(ob) ret.append(len(d)) else: # 找到第一个大于ob的位置 pos = bisect.bisect_right(d, ob) # 替换该位置的值 d[pos] = ob # 结果为位置+1（因为序列从0开始） ret.append(pos + 1) return ret

4、复杂度分析

• 时间复杂度：O(n log n)，每个元素最多进行一次二分查找
• 空间复杂度：O(n)，用于存储维护序列和结果

5、最长公共子序列

Q26、最长公共子序列

1、题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，\"ace\" 是 \"abcde\" 的子序列，但 \"aec\" 不是 \"abcde\" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = \"abcde\", text2 = \"ace\" 输出：3 解释：最长公共子序列是 \"ace\" ，它的长度为 3 。

示例 2：

输入：text1 = \"abc\", text2 = \"abc\"输出：3解释：最长公共子序列是 \"abc\" ，它的长度为 3 。

示例 3：

输入：text1 = \"abc\", text2 = \"def\"输出：0解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

2、解题思路

动态规划方法

1. 定义状态：dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度
2. 状态转移方程 ：
   • 当text1[i-1] == text2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
   • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 初始化 ：
   • dp[0][j] = 0（空字符串与任何字符串的LCS为0）
   • dp[i][0] = 0（同上）
4. 结果：dp[m][n]（m和n分别为text1和text2的长度）

3、代码实现

C++

// 方法1: 动态规划 二维数组class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1] + 1; } else {  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }};

// 方法1: 动态规划 一维数组class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector prev(n + 1, 0), curr(n + 1, 0); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[j - 1]) {  curr[j] = prev[j - 1] + 1; } else {  curr[j] = max(prev[j], curr[j - 1]); } } swap(prev, curr); } return prev[n]; }};

Java

class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int 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]; }}

Python

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) prev = [0] * (n + 1) for i in range(1, m + 1): curr = [0] * (n + 1) for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]:  curr[j] = prev[j - 1] + 1 else:  curr[j] = max(prev[j], curr[j - 1]) prev = curr return prev[n]

4、复杂度分析

• 时间复杂度：O(m×n)，其中m和n是两个字符串的长度
• 空间复杂度：O(m×n)（可优化为O(min(m,n))）

Q27、不相交的线

1、题目描述

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]输出：2解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]输出：2

提示：

• 1 <= nums1.length, nums2.length <= 500
• 1 <= nums1[i], nums2[j] <= 2000

2、解题思路

动态规划法

这个问题实际上是求两个序列的最长公共子序列(LCS)问题。因为：

1. 相等的数字才能连接
2. 连线不能交叉意味着必须保持顺序

状态定义

dp[i][j]表示nums1前i个元素和nums2前j个元素的最长公共子序列长度

状态转移

1. 当nums1[i-1] == nums2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
2. 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3、代码实现

C++

class Solution {public: int maxUncrossedLines(vector& nums1, vector& nums2) { int m = nums1.size(), n = nums2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) {  // 当前数字相等, 可以连接, 长度 +1  dp[i][j] = dp[i - 1][j - 1] + 1; } else {  // 当前数字不等, 取上方或左方的最大值  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }};

Java

class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (nums1[i - 1] == nums2[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]; }}

Python

class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if nums1[i - 1] == nums2[j - 1]:  dp[i][j] = dp[i - 1][j - 1] + 1 else:  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]

4、复杂度分析

• 时间复杂度：O(mn)，其中m和n分别是两个数组的长度
• 空间复杂度：O(mn)，用于存储DP表

Q28、让字符串成为回文串的最少插入次数

1、题目描述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = \"zzazz\"输出：0解释：字符串 \"zzazz\" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = \"mbadm\"输出：2解释：字符串可变为 \"mbdadbm\" 或者 \"mdbabdm\" 。

示例 3：

输入：s = \"leetcode\"输出：5解释：插入 5 个字符后字符串变为 \"leetcodocteel\" 。

提示：

• 1 <= s.length <= 500
• s 中所有字符都是小写字母。

2、解题思路

动态规划法

这个问题可以转化为求字符串与它的反串的最长公共子序列 (LCS)，然后用字符串长度减去 LCS 长度即为答案。但更高效的方法是直接计算最少插入次数：

1. 状态定义：dp[i][j]表示将子串s[i..j]变为回文串所需的最少插入次数
2. 状态转移 ：
   • 如果s[i] == s[j]：dp[i][j] = dp[i+1][j-1]
   • 否则：dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
3. 初始化：所有长度为1的子串已经是回文(dp[i][i] = 0)
4. 结果：dp[0][n-1]表示整个字符串变为回文所需的最少插入次数

3、代码实现

C++

// 方法1: 从后向前填充class Solution {public: int minInsertions(string s) { int n = s.size(); vector<vector> dp(n, vector(n, 0)); for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { if (s[i] == s[j]) {  // 两端字符相同, 不需要额外插入  dp[i][j] = dp[i + 1][j - 1]; } else {  // 两端字符不同, 选择左边或右边插入的最小值  dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; } } } return dp[0][n - 1]; }};

// 方法2: 按子串长度填充class Solution {public: int minInsertions(string s) { int n = s.size(); vector<vector> dp(n, vector(n, 0)); for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (s[i] == s[j]) {  // 两端字符相同  dp[i][j] = dp[i + 1][j - 1]; } else {  // 两端字符不同  dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; } } } return dp[0][n - 1]; }};

Java

class Solution { public int minInsertions(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) {  dp[i][j] = dp[i + 1][j - 1]; } else {  dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; } } } return dp[0][n - 1]; }}

Python

class Solution: def minInsertions(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i+1, n): if s[i] == s[j]:  dp[i][j] = dp[i+1][j-1] else:  dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 return dp[0][n-1]

4、复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的DP表
• 空间复杂度：O(n²)，存储DP表

6、买卖股票的最佳时间/状态机

Q29、买卖股票的最佳时机含冷冻期

1、题目描述

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]输出: 0

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

2、解题思路

动态规划法

我们需要考虑三种状态：

1. 持有股票：可能是前一天就持有，或者是今天买入（前一天不能是冷冻期）
2. 不持有股票且处于冷冻期：只能是今天卖出股票
3. 不持有股票且不处于冷冻期：可能是前一天就不持有且不处于冷冻期，或者是冷冻期结束

状态转移方程

1.  dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])

   • 保持持有状态或从非冷冻期买入

2.  dp[i][1] = dp[i-1][0] + prices[i]

   • 卖出股票进入冷冻期

3.  dp[i][2] = max(dp[i-1][2], dp[i-1][1])

   • 保持非冷冻状态或冷冻期结束

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int maxProfit(vector& prices) { int n = prices.size(); if (n == 0) { return 0; } // dp[i][0]: 持有股票 // dp[i][1]: 不持有股票, 处于冷冻期 // dp[i][2]: 不持有股票, 不处在冷冻期 vector<vector> dp(n, vector(3)); dp[0][0] = -prices[0]; // 第一天买入 for (int i = 1; i < n; ++i) { // 持有股票: 保持持有从非冷冻期买入 dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]); // 处于冷冻期: 只能是今天卖出股票 dp[i][1] = dp[i - 1][0] + prices[i]; // 不处于冷冻期: 保持状态或冷冻期结束 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1]); } return max(dp[n - 1][1], dp[n - 1][2]); }};

// 方法2: 动态规划空间优化class Solution {public: int maxProfit(vector& prices) { int n = prices.size(); if (n == 0) { return 0; } int hold = -prices[0]; // 持有股票 int frozen = 0; // 处于冷冻期 int nohold = 0; // 不持有且不处于冷冻期 for (int i = 1; i < n; ++i) { int new_hold = max(hold, nohold - prices[i]); int new_frozen = hold + prices[i]; int new_nohold = max(nohold, frozen); hold = new_hold; frozen = new_frozen; nohold = new_nohold; } return max(frozen, nohold); }};

Java

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

Python

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) if n == 0: return 0 # 初始化状态 hold = -prices[0] # 持有股票 frozen = 0 # 处于冷冻期 nohold = 0 # 不持有且不处于冷冻期 for i in range(1, n): new_hold = max(hold, nohold - prices[i]) new_frozen = hold + prices[i] new_nohold = max(nohold, frozen) hold, frozen, nohold = new_hold, new_frozen, new_nohold return max(frozen, nohold)

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次价格数组
• 空间复杂度：O(n)（二维DP表）或O(1)（空间优化版本）

Q30、买卖股票的最佳时机含手续费

1、题目描述

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2输出：8解释：能够达到的最大利润: 在此处买入 prices[0] = 1在此处卖出 prices[3] = 8在此处买入 prices[4] = 4在此处卖出 prices[5] = 9总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3输出：6

提示：

• 1 <= prices.length <= 5 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

2、解题思路

动态规划法

我们需要考虑两种状态：

1. 持有股票：可能是前一天就持有，或者是今天买入（前一天不持有）
2. 不持有股票：可能是前一天就不持有，或者是今天卖出（需支付手续费）

状态转移方程

1.  dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

   • 保持持有状态或从不持有状态买入

2.  dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)

   • 保持不持有状态或卖出股票（扣除手续费）

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int maxProfit(vector& prices, int fee) { int n = prices.size(); if (n < 2) { return 0; } // dp[i][0]: 第 i 天持有股票的最大收益 // dp[i][1]: 第 i 天不持有股票的最大收益 vector<vector> dp(n, vector(2)); dp[0][0] = -prices[0]; // 第一天买入 for (int i = 1; i < n; ++i) { // 持有股票: 保持持有或从不持有状态买入 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 不持有股票: 保持不持有或卖出 (扣除手续费) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee); } return dp[n - 1][1]; }};

// 方法2: 动态规划空间优化class Solution {public: int maxProfit(vector& prices, int fee) { int n = prices.size(); if (n < 2) { return 0; } int hold = -prices[0]; // 持有股票 int cash = 0; // 不持有股票 for (int i = 1; i < n; ++i) { int prev_hold = hold; // 更新持有状态 hold = max(hold, cash - prices[i]); // 更新不持有状态 cash = max(cash, prev_hold + prices[i] - fee); } return cash; }};

// 方法3: 贪心算法class Solution {public: int maxProfit(vector& prices, int fee) { int buy = prices[0] + fee; // 初始买入成本 int profit = 0; for (int price : prices) { if (price + fee  buy) { profit += price - buy; // 卖出获利 buy = price; // 更新买入点为当前价格 (相当于免手续费买入) } } return profit; }};// 上面的贪心思想可以浓缩成一句话，即当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。假买假卖。

Java

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

Python

class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) if n < 2: return 0 # 初始化状态 hold = -prices[0] # 持有股票 cash = 0 # 不持有股票 for i in range(1, n): prev_hold = hold # 更新持有状态 hold = max(hold, cash - prices[i]) # 更新不持有状态 cash = max(cash, prev_hold + prices[i] - fee) return cash

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次价格数组
• 空间复杂度：O(n)（二维DP表）或O(1)（空间优化版本）

Q31、买卖股票的最佳时机 III

1、题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]输出：6解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]输出：0

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

2、解题思路

动态规划法（状态机）

我们可以将问题分解为四个状态：

1. 第一次买入：buy1
2. 第一次卖出：sell1
3. 第二次买入：buy2
4. 第二次卖出：sell2

状态转移方程：

1.  buy1 = max(buy1, -prices[i])

   • 保持第一次买入状态或第一次买入当前股票

2.  sell1 = max(sell1, buy1 + prices[i])

   • 保持第一次卖出状态或卖出第一次买入的股票

3.  buy2 = max(buy2, sell1 - prices[i])

   • 保持第二次买入状态或用第一次卖出的利润买入当前股票

4.  sell2 = max(sell2, buy2 + prices[i])

   • 保持第二次卖出状态或卖出第二次买入的股票

3、代码实现

C++

// 方法1: 状态机 (四变量)class Solution {public: int maxProfit(vector& prices) { int n = prices.size(); if (n < 2) { return 0; } int buy1 = -prices[0], sell1 = 0; // 第一次交易状态 int buy2 = -prices[0], sell2 = 0; // 第二次交易状态 for (int i = 1; i < n; ++i) { // 更新第一次买入: 保持原状态或第一次买入当前股票 buy1 = max(buy1, -prices[i]); // 更新第一次卖出: 保持原状态或卖出第一次买入的股票 sell1 = max(sell1, buy1 + prices[i]); // 更新第二次买入: 保持原状态或用第一次利润买入当前股票 buy2 = max(buy2, sell1 - prices[i]); // 更新第二次卖出: 保持原状态或卖出第二次买入的股票 sell2 = max(sell2, buy2 + prices[i]); } return sell2; }};

// 方法2: 通用 K 次交易 DPclass Solution {private: const int INF = 0x3f3f3f3f; // 表示无穷大public: int maxProfit(vector& prices) { int n = prices.size(); if (n < 2) { return 0; } // f[i][j]: 第 i 天第 j 次买入时的最大利润 // g[i][j]: 第 i 天第 j 次卖出时的最大利润 vector<vector> f(n, vector(3, -INF)), g(n, vector(3, -INF)); // 初始化 f[0][0] = -prices[0], g[0][0] = 0; for (int i = 1; i < n; ++i) { for (int j = 0; j = 1) {  g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]); } } } return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2])); }};

// 方法3: K 次交易模板class Solution {public: int maxProfit(vector& prices) { int k = 2; // 交易 k 次 vector buy(k + 1, INT_MIN), sell(k + 1, 0); for (int price : prices) { for (int i = 1; i <= k; ++i) { buy[i] = max(buy[i], sell[i - 1] - price); sell[i] = max(sell[i], buy[i] + price); } } return sell[k]; }};

Java

class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } int buy1 = -prices[0], sell1 = 0; int buy2 = -prices[0], sell2 = 0; for (int i = 1; i < n; i++) { buy1 = Math.max(buy1, -prices[i]); sell1 = Math.max(sell1, buy1 + prices[i]); buy2 = Math.max(buy2, sell1 - prices[i]); sell2 = Math.max(sell2, buy2 + prices[i]); } return sell2; }}

Python

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) if n < 2: return 0 buy1, sell1 = -prices[0], 0 buy2, sell2 = -prices[0], 0 for i in range(1, n): buy1 = max(buy1, -prices[i]) sell1 = max(sell1, buy1 + prices[i]) buy2 = max(buy2, sell1 - prices[i]) sell2 = max(sell2, buy2 + prices[i]) return sell2

4、复杂度分析

• 时间复杂度：O(n)，只需遍历一次价格数组
• 空间复杂度：O(1)，只需要常数空间存储状态

Q32、买卖股票的最佳时机 IV

1、题目描述

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]输出：2解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]输出：7解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

2、解题思路

动态规划法

定义两个状态数组：

1. buy[j]：完成j次交易后处于买入状态的最大利润
2. sell[j]：完成j次交易后处于卖出状态的最大利润

状态转移方程：

1.  buy[j] = max(buy[j], sell[j-1] - price)

   • 保持买入状态或从j-1次交易卖出后买入

2.  sell[j] = max(sell[j], buy[j] + price)

   • 保持卖出状态或从j次交易买入后卖出

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int maxProfit(int k, vector& prices) { int n = prices.size(); if (n < 2) { return 0; } // 优化: 最多进行 n/2 次完整交易 k = min(k, n / 2); // dp[i][0][j]: 第i天持有股票，已完成j次交易 // dp[i][1][j]: 第i天不持有股票，已完成j次交易 vector<vector<vector>> dp( n, vector<vector>(2, vector(k + 1, INT_MIN / 2))); // 初始化 dp[0][0][0] = -prices[0], dp[0][1][0] = 0; for (int i = 1; i < n; ++i) { for (int j = 0; j = 1) {  dp[i][1][j] = max(dp[i][1][j], dp[i - 1][0][j - 1] + prices[i]); } } } // 返回所有可能交易次数中的最大值 return *max_element(dp[n - 1][1].begin(), dp[n - 1][1].end()); }};

// 方法2: 动态规划空间优化class Solution {public: int maxProfit(int k, vector& prices) { int n = prices.size(); if (n < 2) { return 0; } k = min(k, n / 2); vector buy(k + 1, INT_MIN), sell(k + 1, 0); for (int price : prices) { for (int i = 1; i <= k; ++i) { buy[i] = max(buy[i], sell[i - 1] - price); sell[i] = max(sell[i], buy[i] + price); } } return sell[k]; }};

Java

class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n < 2) { return 0; } k = Math.min(k, n / 2); int[] buy = new int[k + 1]; int[] sell = new int[k + 1]; Arrays.fill(buy, Integer.MIN_VALUE / 2); buy[0] = -prices[0]; sell[0] = 0; for (int i = 1; i < n; i++) { for (int j = k; j > 0; j--) { sell[j] = Math.max(sell[j], buy[j] + prices[i]); buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]); } buy[0] = Math.max(buy[0], -prices[i]); } return Arrays.stream(sell).max().getAsInt(); }}

4、复杂度分析

• 时间复杂度：O(n*k)，n为价格天数，k为交易次数
• 空间复杂度：O(k)，只需要存储k次交易的状态

7、动态规划在树的应用

Q33、不同的二叉搜索树

1、题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3输出：5

示例 2：

输入：n = 1输出：1

提示：

• 1 <= n <= 19

2、解题思路

动态规划法

二叉搜索树的数量实际上是卡塔兰数(Catalan Number)，可以使用动态规划求解：

1. 定义 dp[i] 表示 i 个节点能构成的 BST 数量
2. 对于 i 个节点的 BST，我们可以选择任意一个节点 j 作为根节点
3. 左子树包含 j-1 个节点，右子树包含 i-j 个节点
4. 因此 dp[i] = sum(dp[j-1] * dp[i-j]) for j from 1 to i

3、代码实现

C++

class Solution {public: int numTrees(int n) { vector dp(n + 1, 0); // dp[i] 表示 i 个节点能构成的 BST 数量 dp[0] = 1; // 空树也算一种情况 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { // 以 j 为根节点, 左子树有 j-1 个节点, 右子树有 i-j 个节点 dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; }};

Java

class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; // 空树算一种情况 for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { // 左子树数量 * 右子树数量 dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; }}

Python

class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 # 空树算一种情况 for i in range(1, n + 1): for j in range(1, i + 1): # 左子树数量 * 右子树数量 dp[i] += dp[j - 1] * dp[i - j] return dp[n]

4、复杂度分析

• 时间复杂度：O(n²)，需要双重循环计算
• 空间复杂度：O(n)，需要存储dp数组

Q34、不同的二叉搜索树 II

1、题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

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

提示：

• 1 <= n <= 8

2、解题思路

递归分治法

1. 对于给定的数值范围 [start, end]，枚举每个可能的根节点i
2. 递归生成所有可能的左子树集合(数值范围 [start, i-1])
3. 递归生成所有可能的右子树集合(数值范围 [i+1, end])
4. 将左右子树组合与根节点连接，形成完整的 BST

3、代码实现

C++

class Solution {public: vector generateTrees(int n) { if (n == 0) { return {}; } return generateTrees(1, n); } vector generateTrees(int start, int end) { vector result; if (start > end) { result.push_back(nullptr); // 空子树 return result; } // 枚举每个数字作为根节点 for (int i = start; i <= end; ++i) { // 生成所有可能的左子树 vector leftSubtrees = generateTrees(start, i - 1); // 生成所有可能的右子树 vector rightSubtrees = generateTrees(i + 1, end); // 组合左右子树与根节点 for (TreeNode* left : leftSubtrees) { for (TreeNode* right : rightSubtrees) {  TreeNode* root = new TreeNode(i);  root->left = left;  root->right = right;  result.push_back(root); } } } return result; }};

Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<TreeNode>(); } return generateSubtrees(1, n); } private List<TreeNode> generateSubtrees(int start, int end) { List<TreeNode> result = new ArrayList<>(); if (start > end) { result.add(null); // 空子树 return result; } for (int i = start; i <= end; i++) { // 生成所有可能的左子树 List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1); // 生成所有可能的右子树 List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end); // 组合左右子树与根节点 for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) {  TreeNode root = new TreeNode(i);  root.left = left;  root.right = right;  result.add(root); } } } return result; }}

Python

class Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: if n == 0: return [] return self.generate_subtrees(1, n) def generate_subtrees(self, start: int, end: int) -> List[TreeNode]: if start > end: return [None] result = [] for i in range(start, end + 1): # 生成所有可能的左子树 left_trees = self.generate_subtrees(start, i - 1) # 生成所有可能的右子树 right_trees = self.generate_subtrees(i + 1, end) # 组合左右子树与根节点 for left in left_trees: for right in right_trees:  root = TreeNode(i)  root.left = left  root.right = right  result.append(root) return result

4、复杂度分析

• 时间复杂度：O(4ⁿ/n^(1/2))，这是卡塔兰数的增长速度
• 空间复杂度：O(4ⁿ/n^(1/2))，用于存储所有可能的 BST

Q35、打家劫舍 III

1、题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个 “父“ 房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]输出: 9解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

• 树的节点数在 [1, 104] 范围内
• 0 <= Node.val <= 104

2、解题思路

动态规划法（树形DP）

1. 定义两个状态：
   • selected[node]：选择抢劫当前节点时的最大金额
   • notSelected[node]：不选择抢劫当前节点时的最大金额
2. 状态转移：
   • 如果选择当前节点，则不能选择其子节点
   • 如果不选择当前节点，则可以选择或不选择其子节点（取最大值）

3、代码实现

C++

// 方法1: 哈希表存储状态class Solution {private: // selected[i] 表示偷 i 节点时的最高偷盗金额 // notSelected[i] 表示不偷 i 节点时的最高偷盗金额 unordered_map selected, notSelected;public: int rob(TreeNode* root) { dfs(root); return max(selected[root], notSelected[root]); } void dfs(TreeNode* node) { if (!node) { return; } dfs(node->left); dfs(node->right); // 选择当前节点, 则不能选择子节点 selected[node] = node->val + notSelected[node->left] + notSelected[node->right]; // 不选择当前节点, 可以选择或不选择子节点 (取最大值 notSelected[node] = max(selected[node->left], notSelected[node->left]) + max(selected[node->right], notSelected[node->right]); }};

// 方法2: 结构体返回状态 (更优)struct SubtreeStatus { int selected; // 选择当前节点的最大金额 int notSelected; // 不选择当前节点的最大金额};class Solution {public: int rob(TreeNode* root) { auto rootStatus = dfs(root); return max(rootStatus.selected, rootStatus.notSelected); } SubtreeStatus dfs(TreeNode* node) { if (!node) { return {0, 0}; } auto left = dfs(node->left); auto right = dfs(node->right); // 选择当前节点, 则不能选择子节点 int selected = node->val + left.notSelected + right.notSelected; // 不选择当前节点, 可以选择或不选择子节点 (取最大值) int notSelected = max(left.selected, left.notSelected) + max(right.selected, right.notSelected); return {selected, notSelected}; }};

Java

class Solution { public int rob(TreeNode root) { int[] rootStatus = dfs(root); return Math.max(rootStatus[0], rootStatus[1]); } private int[] dfs(TreeNode node) { if (node == null) { return new int[] { 0, 0 }; } int[] left = dfs(node.left); int[] right = dfs(node.right); int selected = node.val + left[1] + right[1]; int notSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); return new int[] { selected, notSelected }; }}

Python

class Solution: def rob(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return (0, 0) left = dfs(node.left) right = dfs(node.right) selected = node.val + left[1] + right[1] not_selected = max(left) + max(right) return (selected, not_selected) return max(dfs(root))

4、复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(n)，递归栈空间

Q36、二叉树中的最大路径和

1、题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

2、解题思路

方法：递归计算

1. 核心思想：

   • 对于每个节点，计算其作为路径\"转折点\"时的最大路径和（即左子树路径+当前节点+右子树路径）
   • 同时计算该节点能提供的最大贡献值（即当前节点值加上左右子树中较大的贡献值）
   • 全局维护一个最大路径和变量

2. 关键点：

   • 路径可以是从任意节点出发到任意节点结束
   • 节点值可能为负，需要处理负贡献情况
   • 递归过程需要返回当前节点的最大贡献值

3、代码实现

C++

class Solution {public: int maxPathSum(TreeNode* root) { maxGain(root); return maxSum; }private: int maxSum = INT_MIN; // 全局变量, 最大路径和 // 计算以 node 为起点的最大贡献值 int maxGain(TreeNode* node) { if (node == nullptr) { return 0; } // 递归计算左右子树的最大贡献值 int leftGain = max(maxGain(node->left), 0); // 如果贡献为负则舍弃 int rightGain = max(maxGain(node->right), 0); // 计算以当前节点为转折点的路径和 int priceNewpath = node->val + leftGain + rightGain; // 更新全局最大路径和 maxSum = max(maxSum, priceNewpath); // 返回当前节点的最大贡献值 (只能选择左右子树的一条路径) return node->val + max(leftGain, rightGain); }};

Java

class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode node) { if (node == null) { return 0; } int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); int newPathSum = node.val + leftGain + rightGain; maxSum = Math.max(maxSum, newPathSum); return node.val + Math.max(leftGain, rightGain); }}

Python

class Solution: def __init__(self): self.max_sum = float(\'-inf\') def maxPathSum(self, root: Optional[TreeNode]) -> int: def max_gain(node): if not node: return 0 left_gain = max(max_gain(node.left), 0) right_gain = max(max_gain(node.right), 0) new_path_sum = node.val + left_gain + right_gain self.max_sum = max(self.max_sum, new_path_sum) return node.val + max(left_gain, right_gain) max_gain(root) return self.max_sum

4、复杂度分析

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，递归栈空间（h为树高）

8、背包问题

Q37、完全平方数

1、题目描述

给你一个整数 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 <= 104

2、解题思路

方法一：动态规划（标准版）

1. 定义状态：dp[i]表示和为i的完全平方数的最少数量
2. 状态转移方程 ：
   • dp[i] = min(dp[i], dp[i - jj] + 1) 对所有jj ≤ i
3. 初始化 ：
   • dp[0] = 0
   • 其他初始化为INT_MAX或较大值

方法二：动态规划（空间优化）

1. 优化空间：使用一维数组代替二维数组
2. 逆向遍历：确保每个平方数只被使用一次

方法三：数学方法（四平方和定理）

1. 四平方和定理：任何自然数都可以表示为最多4个平方数的和
2. 特殊情况处理 ：
   • 如果n是平方数，返回1
   • 如果n满足特定形式，返回4
   • 否则尝试返回2或3

3、代码实现

C++

class Solution {public: int numSquares(int n) { int m = sqrt(n); vector<vector> dp(m + 1, vector(n + 1)); for (int j = 1; j <= n; ++j) { dp[0][j] = INT_MAX / 2; } for (int i = 1; i <= m; ++i) { for (int j = 0; j = i * i) {  dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1); } } } return dp[m][n]; }};

class Solution {public: int numSquares(int n) { vector dp(n + 1, INT_MAX); // dp 数组初始化为最大值 dp[0] = 0;// 和为 0 需要 0 个平方数 // 计算每个 i 的最小平方数 for (int i = 1; i <= n; ++i) { // 遍历所有可能的平方数 for (int j = 1; j * j <= i; ++j) { dp[i] = min(dp[i], dp[i - j * j] + 1); // 状态转移方程 } } return dp[n]; }};

Java

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

Python

class Solution: def numSquares(self, n: int) -> int: dp = [float(\'inf\')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): j = 1 while j * j <= i: dp[i] = min(dp[i], dp[i - j * j] + 1) j += 1 return dp[n]

4、复杂度分析

• 时间复杂度：O(n√n)，需要计算√n次内循环
• 空间复杂度：O(n)，存储dp数组

Q38、零钱兑换 II

1、题目描述

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]输出：0解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

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

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

2、解题思路

动态规划法

1. 完全背包问题：每种硬币可以被选择多次
2. 状态定义：dp[i][j]表示使用前i种硬币凑成金额j的组合数
3. 状态转移 ：
   • 不使用当前硬币：dp[i-1][j]
   • 使用当前硬币：dp[i][j-coins[i-1]]（因为可以重复使用）
4. 优化空间到一维数组

3、代码实现

C++

// 方法1: 二维 DPclass Solution {public: int change(int amount, vector& coins) { int n = coins.size(); vector<vector> dp(n + 1, vector(amount + 1, 0)); // 初始化: 金额为 0 时只有一种组合方式 (不选任何硬币) for (int i = 0; i <= n; ++i) { dp[i][0] = 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j = coins[i - 1] && dp[i][j] < INT_MAX - dp[i][j - coins[i - 1]]) {  dp[i][j] += dp[i][j - coins[i - 1]]; } } } return dp[n][amount]; }};

// 方法2: 一维 DPclass Solution {public: int change(int amount, vector& coins) { vector dp(amount + 1); dp[0] = 1; // 金额为 0 时有 1 中组合方式 for (int coin : coins) { // 从当前硬币面值开始更新 for (int j = coin; j <= amount; ++j) { if (dp[j] < INT_MAX - dp[j - coin]) {  dp[j] += dp[j - coin]; } } } return dp[amount]; }};

Java

class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int j = coin; j <= amount; j++) { dp[j] += dp[j - coin]; } } return dp[amount]; }}

Python

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin] return dp[amount]

4、复杂度分析

• 时间复杂度：O(n×amount)，n为硬币种类数
• 空间复杂度：O(amount)，优化后为一维数组

Q39、组合总和 Ⅳ

1、题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4输出：7解释：所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

2、解题思路

3、代码实现

C++

class Solution {public: int combinationSum4(vector& nums, int target) { vector dp(target + 1, 0); // 使用 unsigned int 避免溢出问题 dp[0] = 1;  // 总和为 0 的组合数为 1 (不选任何元素) for (int i = 1; i = num) {  dp[i] += dp[i - num]; } } } return dp[target]; }};

Java

class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) {  dp[i] += dp[i - num]; } } } return dp[target]; }}

Python

class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target + 1) dp[0] = 1 for i in range(1, target + 1): for num in nums: if i >= num:  dp[i] += dp[i - num] return dp[target]

4、复杂度分析

• 时间复杂度：O(target × n)，n为数组长度
• 空间复杂度：O(target)，用于存储dp数组

Q40、一和零

1、题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [\"10\", \"0001\", \"111001\", \"1\", \"0\"], m = 5, n = 3输出：4解释：最多有 5 个 0 和 3 个 1 的最大子集是 {\"10\",\"0001\",\"1\",\"0\"} ，因此答案是 4 。其他满足题意但较小的子集包括 {\"0001\",\"1\"} 和 {\"10\",\"1\",\"0\"} 。{\"111001\"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = [\"10\", \"0\", \"1\"], m = 1, n = 1输出：2解释：最大的子集是 {\"0\", \"1\"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 \'0\' 和 \'1\' 组成
• 1 <= m, n <= 100

2、解题思路

动态规划法（三维DP）

1. 状态定义：dp[i][j][k]表示前i个字符串中使用j个0和k个1能组成的最大子集长度
2. 状态转移 ：
   • 不选当前字符串：dp[i-1][j][k]
   • 选当前字符串（如果0和1的数量足够）：dp[i-1][j-a][k-b] + 1
3. 初始化：dp[0][j][k] = 0（没有字符串可选）

优化空间（二维DP）

1. 使用倒序更新避免覆盖之前的状态
2. 状态定义：dp[j][k]表示使用j个0和k个1能组成的最大子集长度

3、代码实现

C++

// 方法1: 三维 DPclass Solution {public: int findMaxForm(vector& strs, int m, int n) { int len = strs.size(); // dp[i][j][k]: 前 i 个字符串中使用 j 个 0 和 k 个 1 的最大子集长度 vector<vector<vector>> dp(len + 1, vector<vector>(m + 1, vector(n + 1, 0))); for (int i = 1; i <= len; ++i) { // 统计当前字符中 0 和 1 的数量 int zeros = count(strs[i - 1].begin(), strs[i - 1].end(), \'0\'); int ones = strs[i - 1].size() - zeros; for (int j = 0; j <= m; ++j) { for (int k = 0; k = zeros && k >= ones) { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);  } } } } return dp[len][m][n]; }};

// 方法2: 优化空间的二维 DPclass Solution {public: int findMaxForm(vector& strs, int m, int n) { // dp[j][k]: 使用 j 个 0 和 k 个 1 的最大子集长度 vector<vector> dp(m + 1, vector(n + 1, 0)); for (const string& str : strs) { // 统计当前字符串中 0 和 1 的数量 int zeros = count(str.begin(), str.end(), \'0\'); int ones = str.size() - zeros; // 倒序更新避免覆盖 for (int j = m; j >= zeros; --j) { for (int k = n; k >= ones; --k) {  dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1); } } } return dp[m][n]; }};

Java

class Solution { public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; for (String str : strs) { int zeros = 0, ones = 0; for (char c : str.toCharArray()) { if (c == \'0\') {  zeros++; } else {  ones++; } } for (int j = m; j >= zeros; j--) { for (int k = n; k >= ones; k--) {  dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1); } } } return dp[m][n]; }}

Python

class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: zeros = s.count(\'0\') ones = len(s) - zeros for j in range(m, zeros - 1, -1): for k in range(n, ones - 1, -1):  dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1) return dp[m][n]

4、复杂度分析

• 时间复杂度：O(l×m×n)，l为字符串数量
• 空间复杂度：
  • 三维DP：O(l×m×n)
  • 二维DP：O(m×n)

9、动态规划 - 一维

Q41、解决智力问题

1、题目描述

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]输出：5解释：解决问题 0 和 3 得到最高分。- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。- 不能解决问题 1 和 2- 解决问题 3 ：获得 2 分总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]输出：7解释：解决问题 1 和 4 得到最高分。- 跳过问题 0- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。- 不能解决问题 2 和 3- 解决问题 4 ：获得 5 分总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

提示：

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

2、解题思路

动态规划法（从后向前）

1. 状态定义：dp[i]表示从第i题到最后一题能获得的最大分数
2. 状态转移 ：
   • 跳过当前题目：dp[i+1]
   • 解决当前题目：points[i] + dp[i + brainpower[i] + 1]
3. 初始化：dp[n] = 0（没有题目时得分为0）
4. 计算顺序：从后向前计算，确保依赖的子问题已经解决

3、代码实现

C++

class Solution {public: long long mostPoints(vector<vector>& questions) { int n = questions.size(); // dp[i] 表示从第 i 题到最后一题能获得的最大分数 vector dp(n + 1, 0); // 从后向前计算 for (int i = n - 1; i >= 0; --i) { // 选择1: 跳过当前题目, 得分为 dp[i+1] // 选择2: 解决当前题目, 得分为当前分数 + 跳过后的最高得分 int next = min(n, i + questions[i][1] + 1); dp[i] = max(dp[i + 1], (long long)questions[i][0] + dp[next]); } return dp[0]; }};

Java

class Solution { public long mostPoints(int[][] questions) { int n = questions.length; long[] dp = new long[n + 1]; for (int i = n - 1; i >= 0; i--) { int next = Math.min(n, i + questions[i][1] + 1); dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[next]); } return dp[0]; }}

Python

class Solution: def mostPoints(self, questions: List[List[int]]) -> int: n = len(questions) dp = [0] * (n + 1) for i in range(n - 1, -1, -1): next_idx = min(n, i + questions[i][1] + 1) dp[i] = max(dp[i + 1], questions[i][0] + dp[next_idx]) return dp[0]

4、复杂度分析

• 时间复杂度：O(n)，n为题目数量
• 空间复杂度：O(n)，用于存储dp数组

Q42、零钱兑换

1、题目描述

给你一个整数数组 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] <= 231 - 1
• 0 <= amount <= 104

2、解题思路

方法一：动态规划（二维数组）

1. 定义状态：dp[i][j]表示使用前i种硬币凑成金额j的最少数量
2. 状态转移方程 ：
   • 不使用当前硬币：dp[i][j] = dp[i-1][j]
   • 使用当前硬币：dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]] + 1)
3. 初始化 ：
   • dp[0][j] = ∞（无法用0种硬币凑出任何金额）
   • dp[i][0] = 0（金额0需要0个硬币）

方法二：动态规划（空间优化）

1. 优化空间：使用一维数组代替二维数组
2. 正向遍历：因为硬币可以无限使用，所以从前向后更新

方法三：动态规划（另一种实现）

1. 初始化：dp数组初始化为MAX=amount+1
2. 状态转移：对于每个金额i，尝试使用所有硬币

3、代码实现

C++

// 方法1: 二维数组class Solution {public: int coinChange(vector& coins, int amount) { int n = coins.size(); vector<vector> dp(n + 1, vector(amount + 1, 0)); // 初始化: 使用 0 种硬币无法凑出任何金额 (除 0 外) for (int j = 1; j <= amount; ++j) { dp[0][j] = INT_MAX / 2; // 防止溢出 } for (int i = 1; i <= n; ++i) { for (int j = 0; j = coins[i - 1]) {  dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1); } } } return dp[n][amount] >= INT_MAX / 2 ? -1 : dp[n][amount]; }};

// 方法2: 空间优化class Solution {public: int coinChange(vector& coins, int amount) { vector dp(amount + 1, INT_MAX / 2); dp[0] = 0; // 金额 0 需要 0 个硬币 for (int coin : coins) { for (int j = coin; j = INT_MAX / 2 ? -1 : dp[amount]; }};

Java

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

Python

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float(\'inf\')] * (amount + 1) dp[0] = 0 for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[amount] if dp[amount] != float(\'inf\') else -1

4、复杂度分析

• 时间复杂度：O(n*amount)，其中n是硬币种类数

• 空间复杂度：

  • 方法一：O(n*amount)
  • 方法二/三：O(amount)

Q43、统计构造好字符串的方案数

1、题目描述

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 \'0\' 在字符串末尾添加 zero 次。
• 将 \'1\' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1输出：8解释：一个可能的好字符串是 \"011\" 。可以这样构造得到：\"\" -> \"0\" -> \"01\" -> \"011\" 。从 \"000\" 到 \"111\" 之间所有的二进制字符串都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2输出：5解释：好字符串为 \"00\" ，\"11\" ，\"000\" ，\"110\" 和 \"011\" 。

提示：

• 1 <= low <= high <= 105
• 1 <= zero, one <= low

2、解题思路

动态规划法

1. 状态定义：f[i]表示构造长度为i的字符串的方案数
2. 状态转移 ：
   • 如果当前长度i >= zero，可以从f[i-zero]添加zero个’0’得到
   • 如果当前长度i >= one，可以从f[i-one]添加one个’1’得到
3. 初始化：f[0] = 1（空字符串的方案数为1）
4. 结果统计：累加所有长度在[low, high]之间的方案数

3、代码实现

C++

class Solution {public: int countGoodStrings(int low, int high, int zero, int one) { const int MOD = 1\'000\'000\'007; int ans = 0; // f[i] 表示构造长度为 i 的字符串的方案数 vector f(high + 1, 0); f[0] = 1; // 空字符串的方案数为 1 for (int i = 1; i = zero) { f[i] = (f[i] + f[i - zero]) % MOD; } // 可以从 i-one 添加 one 个 \'1\' 得到当前长度 if (i >= one) { f[i] = (f[i] + f[i - one]) % MOD; } // 如果当前长度在 [low, high] 范围内, 累加到结果 if (i >= low) { ans = (ans + f[i]) % MOD; } } return ans; }};

Java

class Solution { public int countGoodStrings(int low, int high, int zero, int one) { final int MOD = 1_000_000_007; int ans = 0; int[] f = new int[high + 1]; f[0] = 1; for (int i = 1; i <= high; i++) { if (i >= zero) { f[i] = (f[i] + f[i - zero]) % MOD; } if (i >= one) { f[i] = (f[i] + f[i - one]) % MOD; } if (i >= low) { ans = (ans + f[i]) % MOD; } } return ans; }}

Python

class Solution: def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int: MOD = 10**9 + 7 ans = 0 f = [0] * (high + 1) f[0] = 1 for i in range(1, high + 1): if i >= zero: f[i] = (f[i] + f[i - zero]) % MOD if i >= one: f[i] = (f[i] + f[i - one]) % MOD if i >= low: ans = (ans + f[i]) % MOD return ans

4、复杂度分析

• 时间复杂度：O(high)，需要计算1到high的所有长度
• 空间复杂度：O(high)，用于存储dp数组

Q44、解码方法

1、题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

\"1\" -> \'A\' \"2\" -> \'B\' ... \"25\" -> \'Y\' \"26\" -> \'Z\'

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（\"2\" 和 \"5\" 与 \"25\"）。

例如，\"11106\" 可以映射为：

• \"AAJF\" ，将消息分组为 (1, 1, 10, 6)
• \"KJF\" ，将消息分组为 (11, 10, 6)
• 消息不能分组为 (1, 11, 06) ，因为 \"06\" 不是一个合法编码（只有 “6” 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = \"12\"输出：2解释：它可以解码为 \"AB\"（1 2）或者 \"L\"（12）。

示例 2：

输入：s = \"226\"输出：3解释：它可以解码为 \"BZ\" (2 26), \"VF\" (22 6), 或者 \"BBF\" (2 2 6) 。

示例 3：

输入：s = \"06\"输出：0解释：\"06\" 无法映射到 \"F\" ，因为存在前导零（\"6\" 和 \"06\" 并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

2、解题思路

动态规划法

1. 状态定义：dp[i]表示前i个字符的解码方法数
2. 状态转移：
   • 当前字符单独解码（如果非零）：dp[i] += dp[i-1]
   • 当前字符和前一个字符组合解码（如果组合在10-26之间）：dp[i] += dp[i-2]
3. 初始化：
   • dp[0] = 1（空字符串有1种解码方式）
   • dp[1] = s[0] != \'0\'（第一个字符不能为0）

3、代码实现

C++

class Solution {public: int numDecodings(string s) { int n = s.size(); vector dp(n); // 处理第一个字符 dp[0] = s[0] != \'0\'; if (n == 1) { return dp[0]; } // 处理前两个字符 if (s[0] != \'0\' && s[1] != \'0\') { dp[1] += 1; } int t = (s[0] - \'0\') * 10 + s[1] - \'0\'; if (t >= 10 && t <= 26) { dp[1] += 1; } // 填充剩余 dp 数组 for (int i = 2; i = 10 && t <= 26) { dp[i] += dp[i - 2]; // 组合解码最后两个字符 } } return dp[n - 1]; }};

Java

class Solution { public int numDecodings(String s) { int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = s.charAt(0) == \'0\' ? 0 : 1; for (int i = 2; i <= n; i++) { // 单独解码当前字符 if (s.charAt(i - 1) != \'0\') { dp[i] += dp[i - 1]; } // 组合解码最后两个字符 int twoDigits = Integer.parseInt(s.substring(i - 2, i)); if (twoDigits >= 10 && twoDigits <= 26) { dp[i] += dp[i - 2]; } } return dp[n]; }}

Python

class Solution: def numDecodings(self, s: str) -> int: n = len(s) dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 if s[0] != \'0\' else 0 for i in range(2, n + 1): # 单独解码当前字符 if s[i-1] != \'0\': dp[i] += dp[i-1] # 组合解码最后两个字符 two_digits = int(s[i-2:i]) if 10 <= two_digits <= 26: dp[i] += dp[i-2] return dp[n]

4、复杂度分析

• 时间复杂度：O(n)，n为字符串长度
• 空间复杂度：O(n)，用于存储dp数组

Q45、最低票价

1、题目描述

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

• 一张 为期一天 的通行证售价为 costs[0] 美元；
• 一张 为期七天 的通行证售价为 costs[1] 美元；
• 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]输出：11解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]输出：17解释：例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 你总共花了 $17，并完成了你计划的每一天旅行。

提示：

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days 按顺序严格递增
• costs.length == 3
• 1 <= costs[i] <= 1000

2、解题思路

方法一：基于天数的动态规划（365天）

1. 状态定义：dp[i]表示从第i天到365天的最低票价
2. 状态转移 ：
   • 如果当天需要旅行：dp[i] = min(dp[i+1]+costs[0], dp[i+7]+costs[1], dp[i+30]+costs[2])
   • 如果当天不需要旅行：dp[i] = dp[i+1]
3. 初始化：dp[366] = 0（超过365天不需要花费）
4. 结果：dp[1]即为从第1天开始的解

方法二：基于旅行日期的动态规划

1. 状态定义：dp[i]表示从第i个旅行日开始的最低票价
2. 状态转移 ：
   • 对于每个旅行日，尝试三种票价的覆盖范围
   • 找到下一个不在当前票覆盖范围内的旅行日
   • dp[i] = min(dp[j1]+costs[0], dp[j7]+costs[1], dp[j30]+costs[2])
3. 初始化：dp[n] = 0（所有旅行日都已覆盖）
4. 结果：dp[0]即为从第一个旅行日开始的解

3、代码实现

C++

// 方法1: 基于天数的动态规划class Solution {private: unordered_set dayset; vector costs; int memo[366] = {0};public: int mincostTickets(vector& days, vector& costs) { this->costs = costs; for (int d : days) { dayset.insert(d); } memset(memo, -1, sizeof(memo)); return dp(1); } int dp(int i) { if (i > 365) { return 0; } if (memo[i] != -1) { return memo[i]; } if (dayset.count(i)) { memo[i] = min(min(dp(i + 1) + costs[0], dp(i + 7) + costs[1]), dp(i + 30) + costs[2]); } else { memo[i] = dp(i + 1); } return memo[i]; }};

// 方法2: 基于旅行日期的动态规划class Solution {private: vector days, costs; vector memo; int durations[3] = {1, 7, 30};public: int mincostTickets(vector& days, vector& costs) { this->days = days; this->costs = costs; memo.assign(days.size(), -1); return dp(0); } int dp(int i) { if (i >= days.size()) { return 0; } if (memo[i] != -1) { return memo[i]; } memo[i] = INT_MAX; int j = i; for (int k = 0; k < 3; ++k) { while (j < days.size() && days[j] < days[i] + durations[k]) { j++; } memo[i] = min(memo[i], dp(j) + costs[k]); } return memo[i]; }};

Java

class Solution { private Set<Integer> dayset = new HashSet<>(); private int[] costs; private int[] memo = new int[366]; public int mincostTickets(int[] days, int[] costs) { this.costs = costs; for (int d : days) { dayset.add(d); } Arrays.fill(memo, -1); return dp(1); } private int dp(int i) { if (i > 365) { return 0; } if (memo[i] != -1) { return memo[i]; } if (dayset.contains(i)) { memo[i] = Math.min(Math.min(dp(i + 1) + costs[0], dp(i + 7) + costs[1]), dp(i + 30) + costs[2]); } else { memo[i] = dp(i + 1); } return memo[i]; }}

class Solution { private int[] days, costs; private int[] memo; private int[] durations = { 1, 7, 30 }; public int mincostTickets(int[] days, int[] costs) { this.days = days; this.costs = costs; memo = new int[days.length]; Arrays.fill(memo, -1); return dp(0); } private int dp(int i) { if (i >= days.length) { return 0; } if (memo[i] != -1) { return memo[i]; } memo[i] = Integer.MAX_VALUE; int j = i; for (int k = 0; k < 3; k++) { while (j < days.length && days[j] < days[i] + durations[k]) { j++; } memo[i] = Math.min(memo[i], dp(j) + costs[k]); } return memo[i]; }}

Python

class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: dayset = set(days) memo = [-1] * 366 def dp(i): if i > 365: return 0 if memo[i] != -1: return memo[i] if i in dayset: memo[i] = min(dp(i+1)+costs[0], dp(i+7)+costs[1], dp(i+30)+costs[2]) else: memo[i] = dp(i+1) return memo[i] return dp(1)

class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: durations = [1, 7, 30] memo = [-1] * len(days) def dp(i): if i >= len(days): return 0 if memo[i] != -1: return memo[i] memo[i] = float(\'inf\') j = i for k in range(3): while j < len(days) and days[j] < days[i] + durations[k]:  j += 1 memo[i] = min(memo[i], dp(j) + costs[k]) return memo[i] return dp(0)

4、复杂度分析

• 方法一：

  • 时间复杂度：O(365)
  • 空间复杂度：O(365)

• 方法二：

  • 时间复杂度：O(n)，n为旅行日数量
  • 空间复杂度：O(n)

Q46、多米诺和托米诺平铺

1、题目描述

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3输出: 5解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1输出: 1

提示：

• 1 <= n <= 1000

2、解题思路

动态规划法

1. 状态定义：定义四种状态表示第i列的不同覆盖情况

   • dp[i][0]：第i列一个正方形都没有被覆盖
   • dp[i][1]：第i列只有上方的正方形被覆盖
   • dp[i][2]：第i列只有下方的正方形被覆盖
   • dp[i][3]：第i列上下两个正方形都被覆盖

2. 状态转移：

   • dp[i][0]只能从dp[i-1][3]转移而来
   • dp[i][1]可以从dp[i-1][0]或dp[i-1][2]转移而来
   • dp[i][2]可以从dp[i-1][0]或dp[i-1][1]转移而来
   • dp[i][3]可以从四种前驱状态转移而来

3. 初始化：

   • 初始状态dp[0][3] = 1（空面板视为完全覆盖）
   • 其他初始状态为0

3、代码实现

C++

class Solution {public: int numTilings(int n) { const long long mod = 1e9 + 7; // dp[i][0]: 第 i 列一个正方形都没有被覆盖 // dp[i][1]: 第 i 列只有上方的正方形被覆盖 // dp[i][2]: 第 i 列只有下方的正方形被覆盖 // dp[i][3]: 第 i 列上下两个正方形都被覆盖 vector<vector> dp(n + 1, vector(4)); dp[0][3] = 1; // 初始状态 for (int i = 1; i <= n; ++i) { // 当前列未被覆盖, 前一列必须完全覆盖 dp[i][0] = dp[i - 1][3] % mod; // 当前列只有上方被覆盖, 可以来自: // 1. 前一列未被覆盖 + 一个 L 形砖 // 2. 前一列只有下方被覆盖 + 一个水平多米诺 dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod; // 当前只有下方被覆盖, 可以来自: // 1. 前一列未被覆盖 + 一个 L 形砖 // 2. 前一列只有上方被覆盖 + 一个水平多米诺 dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod; // 当前列完全被覆盖, 可以来自: // 1. 前一列未被覆盖 + 两个垂直多米诺 // 2. 前一列只有上方被覆盖 + 一个 L 形砖 // 3. 前一列只有下方被覆盖 + 一个 L 形砖 // 4. 前一列完全被覆盖 + 一个水平多米诺 dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod; } return dp[n][3]; }};

Java

class Solution { public int numTilings(int n) { final long mod = (long) 1e9 + 7; long[][] dp = new long[n + 1][4]; dp[0][3] = 1; for (int i = 1; i <= n; i++) { dp[i][0] = dp[i - 1][3] % mod; dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod; dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod; dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod; } return (int) dp[n][3]; }}

Python

class Solution: def numTilings(self, n: int) -> int: mod = 10**9 + 7 dp = [[0] * 4 for _ in range(n + 1)] dp[0][3] = 1 for i in range(1, n + 1): dp[i][0] = dp[i - 1][3] % mod dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod return dp[n][3]

4、复杂度分析

• 时间复杂度：O(n)，需要遍历1到n
• 空间复杂度：O(n)，用于存储dp数组

10、动态规划 - 多维

Q47、粉刷房子

1、题目描述

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]输出: 10解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。 最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]输出: 2

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

2、解题思路

动态规划法

1. 状态定义：dp[n][color] 表示第 n 个房子粉刷成 color 颜色时的最小总成本
2. 状态转移 ：
   • 当前房子颜色不能与前一个房子颜色相同
   • dp[n][0] = costs[n][0] + min(dp[n+1][1], dp[n+1][2])
   • dp[n][1] = costs[n][1] + min(dp[n+1][0], dp[n+1][2])
   • dp[n][2] = costs[n][2] + min(dp[n+1][0], dp[n+1][1])
3. 初始化：最后一个房子的成本即为costs[n-1][color]
4. 结果：min(dp[0][0], dp[0][1], dp[0][2])

3、代码实现

C++

// 方法1: 递归 + 记忆化 (自上而下)class Solution {public: int minCost(vector<vector>& costs) { if (costs.empty()) { return 0; } unordered_map memo; function paintCost = [&](int n, int color) { int key = (n << 2) + color; // 编码键值 if (memo.count(key)) { return memo[key]; } int totalCost = costs[n][color]; if (n != costs.size() - 1) { if (color == 0) // 红色 {  totalCost += min(paintCost(n + 1, 1), paintCost(n + 1, 2)); } else if (color == 1) // 绿色 {  totalCost += min(paintCost(n + 1, 0), paintCost(n + 1, 2)); } else // 蓝色 {  totalCost += min(paintCost(n + 1, 0), paintCost(n + 1, 1)); } } memo[key] = totalCost; return totalCost; }; return min({paintCost(0, 0), paintCost(0, 1), paintCost(0, 2)}); }};

// 方法2: 动态规划 (自下而上)class Solution {public: int minCost(vector<vector>& costs) { if (costs.empty()) { return 0; } for (int n = costs.size() - 2; n >= 0; --n) { // 红色: 当前成本 + 下一栋绿色或蓝色的最小成本 costs[n][0] += min(costs[n + 1][1], costs[n + 1][2]); // 绿色: 当前成本 + 下一栋红色或蓝色的最小成本 costs[n][1] += min(costs[n + 1][0], costs[n + 1][2]); // 蓝色: 当前成本 + 下一栋红色或绿色的最小成本 costs[n][2] += min(costs[n + 1][0], costs[n + 1][1]); } return min({costs[0][0], costs[0][1], costs[0][2]}); }};

// 方法3: 动态规划空间优化class Solution {public: int minCost(vector<vector>& costs) { if (costs.empty()) { return 0; } vector prevRow = costs.back(); for (int n = costs.size() - 2; n >= 0; --n) { vector currentRow = costs[n]; currentRow[0] += min(prevRow[1], prevRow[2]); currentRow[1] += min(prevRow[0], prevRow[2]); currentRow[2] += min(prevRow[0], prevRow[1]); prevRow = currentRow; } return *min_element(prevRow.begin(), prevRow.end()); }};

Java

class Solution { public int minCost(int[][] costs) { if (costs == null || costs.length == 0) { return 0; } for (int n = costs.length - 2; n >= 0; n--) { costs[n][0] += Math.min(costs[n + 1][1], costs[n + 1][2]); costs[n][1] += Math.min(costs[n + 1][0], costs[n + 1][2]); costs[n][2] += Math.min(costs[n + 1][0], costs[n + 1][1]); } return Math.min(Math.min(costs[0][0], costs[0][1]), costs[0][2]); }}

Python

class Solution: def minCost(self, costs: List[List[int]]) -> int: if not costs: return 0 for n in range(len(costs)-2, -1, -1): costs[n][0] += min(costs[n+1][1], costs[n+1][2]) costs[n][1] += min(costs[n+1][0], costs[n+1][2]) costs[n][2] += min(costs[n+1][0], costs[n+1][1]) return min(costs[0])

4、复杂度分析

• 时间复杂度：O(n)，需要遍历所有房子
• 空间复杂度：O(1)，优化后只需保存前一行的状态

Q48、粉刷房子 II

1、题目描述

假如有一排房子共有 n 幢，每个房子可以被粉刷成 k 种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

每个房子粉刷成不同颜色的花费以一个 n x k 的矩阵表示。

• 例如，costs[0][0] 表示第 0 幢房子粉刷成 0 号颜色的成本；costs[1][2] 表示第 1 幢房子粉刷成 2 号颜色的成本，以此类推。

返回 粉刷完所有房子的最低成本 。

示例 1：

输入: costs = [[1,5,3],[2,9,4]]输出: 5解释: 将房子 0 刷成 0 号颜色，房子 1 刷成 2 号颜色。花费: 1 + 4 = 5; 或者将 房子 0 刷成 2 号颜色，房子 1 刷成 0 号颜色。花费: 3 + 2 = 5. 

示例 2:

输入: costs = [[1,3],[2,4]]输出: 5

提示：

• costs.length == n
• costs[i].length == k
• 1 <= n <= 100
• 2 <= k <= 20
• 1 <= costs[i][j] <= 20

**进阶：**您能否在 O(nk) 的时间复杂度下解决此问题？

2、解题思路

动态规划法

1. 状态定义：dp[i][j]表示第i个房子涂第j种颜色的最小总成本
2. 状态转移 ：
   • 当前房子颜色不能与前一个房子颜色相同
   • dp[i][j] = costs[i][j] + min(dp[i-1][0], ..., dp[i-1][k])(排除颜色j)
3. 优化思路 ：
   • 记录前一行的最小值和次小值，避免每次遍历
   • 如果当前颜色与前一行最小值颜色相同，则使用次小值

3、代码实现

C++

// 方法1: 递归 + 记忆化class Solution {public: int minCostII(vector<vector>& costs) { int n = costs.size(); if (n == 0) { return 0; } int k = costs[0].size(); map memo; auto hash = [&](int x, int y) -> long long { return ((long long)x << 32) + y; }; function memoSlove = [&](int houseNum, int color) -> int { // 边界条件 if (houseNum == n - 1) { return costs[houseNum][color]; } long long key = hash(houseNum, color); if (memo.count(key)) { return memo[key]; } // 递归条件 int cost = INT_MAX; for (int nextColor = 0; nextColor < k; ++nextColor) { if (nextColor == color) {  continue; // 不能给相邻的房子涂同样的颜色 } cost = min(cost, memoSlove(houseNum + 1, nextColor)); } memo[key] = costs[houseNum][color] + cost; return memo[key]; }; // 考虑粉刷 0 号房子的所有选项, 找出最小值 int cost = INT_MAX; for (int color = 0; color < k; ++color) { cost = min(cost, memoSlove(0, color)); } return cost; }};

// 方法2: 动态规划基础版class Solution {public: int minCostII(vector<vector>& costs) { if (costs.empty()) { return 0; } int n = costs.size(), k = costs[0].size(); for (int i = 1; i < n; ++i) { for (int j = 0; j < k; ++j) { int min_val = INT_MAX; for (int m = 0; m < k; ++m) {  if (m == j) { continue;  }  min_val = min(min_val, costs[i - 1][m]); } costs[i][j] += min_val; } } return *min_element(costs.back().begin(), costs.back().end()); }};

// 方法3: 动态规划空间优化版class Solution {public: int minCostII(vector<vector>& costs) { if (costs.empty()) { return 0; } int n = costs.size(), k = costs[0].size(); vector prev = costs[0]; for (int i = 1; i < n; ++i) { vector curr(k, 0); for (int j = 0; j < k; ++j) { int min_val = INT_MAX; for (int m = 0; m < k; ++m) {  if (m == j) { continue;  }  min_val = min(min_val, prev[m]); } curr[j] = costs[i][j] + min_val; } prev = curr; } return *min_element(prev.begin(), prev.end()); }};

// 方法4: 动态规划时间优化版class Solution {public: int minCostII(vector<vector>& costs) { if (costs.empty()) { return 0; } int n = costs.size(), k = costs[0].size(); int min1 = 0, min2 = 0, min_color = -1; for (int i = 0; i < n; ++i) { int curr_min1 = INT_MAX, curr_min2 = INT_MAX, curr_color = -1; for (int j = 0; j < k; ++j) { int cost = costs[i][j] + (j == min_color ? min2 : min1); if (cost < curr_min1) {  curr_min2 = curr_min1;  curr_min1 = cost;  curr_color = j; } else if (cost < curr_min2) {  curr_min2 = cost; } } min1 = curr_min1; min2 = curr_min2; min_color = curr_color; } return min1; }};

Java

class Solution { public int minCostII(int[][] costs) { if (costs == null || costs.length == 0) return 0; int n = costs.length, k = costs[0].length; int min1 = 0, min2 = 0, minColor = -1; for (int i = 0; i < n; i++) { int currMin1 = Integer.MAX_VALUE, currMin2 = Integer.MAX_VALUE, currColor = -1; for (int j = 0; j < k; j++) { int cost = costs[i][j] + (j == minColor ? min2 : min1); if (cost < currMin1) {  currMin2 = currMin1;  currMin1 = cost;  currColor = j; } else if (cost < currMin2) {  currMin2 = cost; } } min1 = currMin1; min2 = currMin2; minColor = currColor; } return min1; }}

Python

class Solution: def minCostII(self, costs: List[List[int]]) -> int: if not costs: return 0 n, k = len(costs), len(costs[0]) min1, min2, min_color = 0, 0, -1 for i in range(n): curr_min1 = curr_min2 = float(\'inf\') curr_color = -1 for j in range(k): cost = costs[i][j] + (min2 if j == min_color else min1) if cost < curr_min1:  curr_min2, curr_min1 = curr_min1, cost  curr_color = j elif cost < curr_min2:  curr_min2 = cost min1, min2, min_color = curr_min1, curr_min2, curr_color return min1

4、复杂度分析

• 时间复杂度：O(nk)，遍历所有房子和颜色
• 空间复杂度：O(1)，优化后只需保存前一行信息

Q49、统计元音字母序列的数目

1、题目描述

给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

• 字符串中的每个字符都应当是小写元音字母（\'a\', \'e\', \'i\', \'o\', \'u\'）
• 每个元音 \'a\' 后面都只能跟着 \'e\'
• 每个元音 \'e\' 后面只能跟着 \'a\' 或者是 \'i\'
• 每个元音 \'i\' 后面 不能 再跟着另一个 \'i\'
• 每个元音 \'o\' 后面只能跟着 \'i\' 或者是 \'u\'
• 每个元音 \'u\' 后面只能跟着 \'a\'

由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

示例 1：

输入：n = 1输出：5解释：所有可能的字符串分别是：\"a\", \"e\", \"i\" , \"o\" 和 \"u\"。

示例 2：

输入：n = 2输出：10解释：所有可能的字符串分别是：\"ae\", \"ea\", \"ei\", \"ia\", \"ie\", \"io\", \"iu\", \"oi\", \"ou\" 和 \"ua\"。

示例 3：

输入：n = 5输出：68

提示：

• 1 <= n <= 2 * 10^4

2、解题思路

方法一：动态规划

1. 状态定义：dp[i][j]表示长度为i的字符串以j元音结尾的数量
2. 状态转移：
   • a可以从e,u,i转移而来
   • e可以从a,i转移而来
   • i可以从e,o转移而来
   • o可以从i转移而来
   • u可以从i,o转移而来
3. 初始化：长度为1时每个元音都有1种可能
4. 结果：所有元音的dp[n]之和

方法二：矩阵快速幂

1. 构建转移矩阵：表示各元音之间的转移关系
2. 矩阵快速幂：计算转移矩阵的(n-1)次幂
3. 结果计算：矩阵元素之和即为总数量

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int countVowelPermutation(int n) { const long long mod = 1e9 + 7; // dp a,e,i,o,u vector dp(5, 1); vector next_dp(5); for (int i = 2; i <= n; ++i) { // \'a\' 可以跟 \'e\', \'u\', \'i\' next_dp[0] = (dp[1] + dp[4] + dp[2]) % mod; // \'e\' 可以跟 \'a\',\'i\' next_dp[1] = (dp[0] + dp[2]) % mod; // \'i\' 可以跟 \'e\',\'o\' next_dp[2] = (dp[1] + dp[3]) % mod; // \'o\' 可以跟 \'i\' next_dp[3] = dp[2] % mod; // \'u\' 可以跟 \'i\',\'o\' next_dp[4] = (dp[2] + dp[3]) % mod; dp = next_dp; } return accumulate(dp.begin(), dp.end(), 0LL) % mod; }};

// 方法2: 矩阵快速幂class Solution {public: int countVowelPermutation(int n) { const long long mod = 1e9 + 7; vector<vector> transition = { {0, 1, 0, 0, 0}, // a 后面跟 e {1, 0, 1, 0, 0}, // e 后面跟 a or i {1, 1, 0, 1, 1}, // i 后面跟 e or o {0, 0, 1, 0, 1}, // o 后面跟 i {1, 0, 0, 0, 0} // u 后面跟 a }; if (n == 1) { return 5; } vector<vector> result = matrixPow(transition, n - 1, mod); long long total = 0; for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { total = (total + result[i][j]) % mod; } } return total; }private: vector<vector> multiply(const vector<vector>& a, const vector<vector>& b, long long mod) { vector<vector> res(5, vector(5)); for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { for (int k = 0; k < 5; ++k) {  res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod; } } } return res; } vector<vector> matrixPow(vector<vector> m, int power, long long mod) { vector<vector> res = { {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1} }; while (power > 0) { if (power & 1) { res = multiply(res, m, mod); } m = multiply(m, m, mod); power >>= 1; } return res; }};

Java

class Solution { public int countVowelPermutation(int n) { long mod = 1000000007; long[] dp = { 1, 1, 1, 1, 1 }; long[] nextDp = new long[5]; for (int i = 2; i <= n; i++) { nextDp[0] = (dp[1] + dp[2] + dp[4]) % mod; nextDp[1] = (dp[0] + dp[2]) % mod; nextDp[2] = (dp[1] + dp[3]) % mod; nextDp[3] = dp[2] % mod; nextDp[4] = (dp[2] + dp[3]) % mod; System.arraycopy(nextDp, 0, dp, 0, 5); } long total = 0; for (long num : dp) { total = (total + num) % mod; } return (int) total; }}

Python

class Solution: def countVowelPermutation(self, n: int) -> int: mod = 10**9 + 7 dp = [1] * 5 # a,e,i,o,u for _ in range(n - 1): a, e, i, o, u = dp new_a = (e + i + u) % mod new_e = (a + i) % mod new_i = (e + o) % mod new_o = i % mod new_u = (i + o) % mod dp = [new_a, new_e, new_i, new_o, new_u] return sum(dp) % mod

4、复杂度分析

• 动态规划：时间O(n)，空间O(1)
• 矩阵快速幂：时间O(logn)，空间O(1)

Q50、从栈中取出 K 个硬币的最大面值和

1、题目描述

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。

每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。

示例 1：

输入：piles = [[1,100,3],[7,8,9]], k = 2输出：101解释：上图展示了几种选择 k 个硬币的不同方法。我们可以得到的最大面值为 101 。

示例 2：

输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7输出：706解释：如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。

提示：

• n == piles.length
• 1 <= n <= 1000
• 1 <= piles[i][j] <= 105
• 1 <= k <= sum(piles[i].length) <= 2000

2、解题思路

动态规划法

1. 状态定义：dp[i]表示进行i次操作能获得的最大面值总和
2. 状态转移：
   • 对于每堆硬币，考虑取1到该堆硬币总数的所有可能性
   • 更新dp数组时从后往前遍历，避免重复计算
3. 初始化：dp[0] = 0，其他初始为-1表示不可达
4. 结果：dp[k]即为答案

3、代码实现

C++

class Solution {public: int maxValueOfCoins(vector<vector>& piles, int k) { vector dp(k + 1, -1); // dp[i] 表示 i 次操作的最大面值 dp[0] = 0;  // 0 次操作面值为 0 // 遍历每一堆硬币 for (const auto& pile : piles) { // 从后往前遍历操作次数 for (int i = k; i >= 0; --i) { // 当前操作次数不可达 if (dp[i] == -1) {  continue; } int sum = 0; for (int j = 1; j <= pile.size() && i + j <= k; ++j) {  sum += pile[j - 1]; // 取 j 个硬币的面值总和  if (dp[i + j] < dp[i] + sum) { dp[i + j] = dp[i] + sum; // 更新最大值  } } } } return dp[k]; }};

Java

class Solution { public int maxValueOfCoins(List<List<Integer>> piles, int k) { int[] dp = new int[k + 1]; Arrays.fill(dp, -1); dp[0] = 0; for (List<Integer> pile : piles) { for (int i = k; i >= 0; i--) { if (dp[i] == -1) {  continue; } int sum = 0; for (int j = 1; j <= pile.size() && i + j <= k; j++) {  sum += pile.get(j - 1);  if (dp[i + j] < dp[i] + sum) { dp[i + j] = dp[i] + sum;  } } } } return dp[k]; }}

Python

class Solution: def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int: dp = [-1] * (k + 1) dp[0] = 0 for pile in piles: for i in range(k, -1, -1): if dp[i] == -1:  continue sum_val = 0 for j in range(1, len(pile) + 1):  if i + j > k: break  sum_val += pile[j - 1]  if dp[i + j] < dp[i] + sum_val: dp[i + j] = dp[i] + sum_val return dp[k]

4、复杂度分析

• 时间复杂度：O(nkm)，其中n为堆数，k为操作次数，m为平均每堆硬币数
• 空间复杂度：O(k)，仅需维护一维dp数组