动态规划

LeetCode 10 https://leetcode.cn/problems/regular-expression-matching/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划。dp[i][j]表示 s[..i]与 p[..j]是否能够匹配。 s[i]==p[j] 或者 p[j]==’.' 此时 dp[i][j] = dp[i-1][j-1] s[i]与 p[j]不匹配，并且 p[j] != ‘*’ 如果 2.1 不成立，并且 p[j]也不是通配符’*’，那没辙了，直接返回匹配失败。 s[i]与 p[j]虽然不匹配，但是 p[j] == ‘*’ 这就要分两种情况了，要看 p[j-1]和 s[i]是否匹配。 如果 p[j-1]和 s[i]不匹配，那’_‘只能把前元素 p[j-1]匹配成 0 个 如果 p[j-1]和 s[i]可以匹配，那’_‘就可以把前元素 p[j-1]匹配成 0 个，1 个，多个。 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 p 的长度。我们需要计算出所有的状态，并且每个状态在进行转移时的时间复杂度为 O(1)。 空间复杂度：O(mn)，即为存储所有状态使用的空间。 ...

LCR 127 https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 跳台阶。 时间复杂度 O(n) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。 空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。 ...

LCR 161 https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题与 LeetCode 53 相同。 这里使用动态规划方法。 f[i + 1] = max(f[i], 0) + sales[i]。 时间复杂度：O(n)，其中 n 为 sales 数组的长度。我们只需要遍历一遍数组即可求得答案。 空间复杂度：O(n)。我们只需要常数空间存放若干变量。 ...

LeetCode 91 https://leetcode.cn/problems/decode-ways/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这是划分型 DP 中的最优划分问题。 计算最少（最多）可以划分出多少段、最优划分得分等。 一般定义 f[i] 表示长为 i 的前缀 a[:i] 在题目约束下，分割出的最少（最多）子数组个数（或者定义成分割方案数）。 枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 对最优解的影响。 本题类似爬楼梯，只是 f[i - 2] 需要判定。 时间复杂度：O(n)，其中 n 是字符串 s 的长度。 空间复杂度：O(n) 或 O(1)。如果使用数组进行状态转移，空间复杂度为 O(n)；如果仅使用三个变量，空间复杂度为 O(1)。 ...

LeetCode 518 https://leetcode.cn/problems/coin-change-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 完全背包题目。 dfs(i, c) = dfs(i − 1, c) + dfs(i, c − coins[i]) 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。 空间复杂度：O(n⋅amount)。 ...

LeetCode 123 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是至少可以完成 k 次交易的股票买卖问题。 数组需要增加一维 k， f[n + 1][k + 2][2]。在买入（或卖出）时将剩余交易次数减一。 初始化 f[0][j][0] = 0，其他元素为 -INF。 时间复杂度：O(n)，其中 n 为 prices 的长度。 空间复杂度：O(1)。 ...

LeetCode 139 https://leetcode.cn/problems/word-break/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 划分型 DP 一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分。 枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 是否满足要求。 这道题首先为了方便判断是否在单词表中，先把 wordDict 转成 unordered_set。另外，本题 wordDict 至多有 1000 个字符串，但最多只有 20 种不同的长度，所以应该枚举长度，而不是枚举 wordDict 中的字符串。 时间复杂度：\(O(mL+nL^2)\)，其中 m 是 wordDict 的长度，L 是 wordDict 中字符串的最长长度，n 是 s 的长度。创建哈希集合需要 O(mL) 的时间。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n)，单个状态的计算时间为 \(O(L^2)\)（注意判断子串是否在哈希集合中需要 O(L) 的时间），所以记忆化搜索的时间复杂度为 \(O(nL^2)\)。 空间复杂度：O(mL+n)。哈希集合需要 O(mL) 的空间。记忆化搜索需要 O(n) 的空间。 ...

LeetCode 718 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 类似最长公共子序列，这题是求连续子数组。定义 f[i+1][j+1] 表示以 nums1[i] 结尾的子数组和以 nums2[j] 结尾的子数组的最长公共子数组的长度。 如果 nums1[i] != nums2[j]，那么 f[i+1][j+1]=0。 如果 nums1[i] == nums2[j]，那么问题变成以 nums1[i−1] 结尾的子数组和以 nums2[j−1] 结尾的子数组的最长公共子数组的长度，即 f[i+1][j+1]=f[i][j]+1。相当于在以 nums1[i−1] 结尾的子数组后面添加 nums1[i]，在以 nums2[j−1] 结尾的子数组后面添加 nums2[j]。 初始值：f[0][j]=f[i][0]=0，空子数组没有公共部分。 答案：所有 f[i][j] 的最大值。 时间复杂度：O(nm)，其中 n 是 nums1 的长度，m 是 nums2 的长度。 空间复杂度：O(nm)。 ...

LeetCode 198 https://leetcode.cn/problems/house-robber/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 状态转移： f[i + 2] = max(f[i + 1], f[i] + nums[i]); 时间复杂度：O(n)。其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...

LeetCode 152 https://leetcode.cn/problems/maximum-product-subarray/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划，类似 LeetCode 53 最大子数组和。由于负负得正，需要维护以 i 结尾的连续子数组乘积的最大值和最小值。 f_max[i] = max({f_max[i - 1] * x, f_min[i - 1] * x, x}); f_min[i] = min({f_max[i - 1] * x, f_min[i - 1] * x, x}); 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(n)。 ...