LeetCode 416 https://leetcode.cn/problems/partition-equal-subset-sum/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题相当于能否从 nums 中选出一个子序列，其元素和恰好等于 s/2。这是 0-1 背包的恰好装满型问题。 dfs(i, j)=dfs(i−1, j−nums[i]) || dfs(i−1, j) 时间复杂度：O(ns)，其中 n 是 nums 的长度，s 是 nums 的元素和（的一半）。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(ns)，单个状态的计算时间为 O(1)，所以动态规划的时间复杂度为 O(ns)。 空间复杂度：O(ns)。保存多少状态，就需要多少空间。 ...
LeetCode 673 https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LC 300 最长递增子序列的升级版。 定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。设 nums 的最长上升子序列的长度为 maxLen，那么答案为所有满足 dp[i]=maxLen 的 i 所对应的 cnt[i] 之和。 对于 cnt[i]，其等于所有满足 dp[j]+1=dp[i] 的 cnt[j] 之和。在代码实现时，我们可以在计算 dp[i] 的同时统计 cnt[i] 的值。 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 97 https://leetcode.cn/problems/interleaving-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ f[i + 1][j + 1] 表示 s3 的前 i + j + 2 个元素能否由 s1 的前 i + 1 个元素和 s2 的前 j + 1 个元素组成。 状态转移条件是 s3 的前 i + j + 1 个元素能否由 s1 的前 i 个元素和 s2 的前 j + 1 个元素组成，或由 s1 的前 i + 1 个元素和 s2 的前 j 个元素组成。 初始值 f[0][0] = 0，并且单独计算 f[i][0] 和 f[0][j]。 时间复杂度：O(nm)。 空间复杂度：O(nm)。 ...
LeetCode 264 https://leetcode.cn/problems/ugly-number-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。 由于最小的丑数是 1，因此 dp[1]=1。 如何得到其余的丑数呢？定义三个指针 p2,p3,p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 1。 当 2≤i≤n 时，令 dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，然后分别比较 dp[i] 和 dp[p2]×2,dp[p3]×3,dp[p5]×5 是否相等，如果相等则将对应的指针加 1。 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ...
LeetCode 44 https://leetcode.cn/problems/wildcard-matching/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划，我们用 dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配。状态转移方程为 if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] | dp[i - 1][j]; } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。 空间复杂度：O(mn)，即为存储所有 (m+1)(n+1) 个状态需要的空间。此外，在状态转移方程中，由于 dp[i][j] 只会从 dp[i][..] 以及 dp[i−1][..] 转移而来，因此我们可以使用滚动数组对空间进行优化，即用两个长度为 n+1 的一维数组代替整个二维数组进行状态转移，空间复杂度为 O(n)。 ...
LeetCode 887 https://leetcode.cn/problems/super-egg-drop/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 定义状态为 dfs(i,j)，表示在有 i 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。 在 dfs(i−1,j−1)+1 楼扔第一枚鸡蛋： 如果鸡蛋碎了，接下来只需要在 [1,dfs(i−1,j−1)] 中扔鸡蛋，就可以确定 f 的值。 如果鸡蛋没碎，问题变成在有 i−1 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。这个子问题的答案 dfs(i−1,j)，加上 dfs(i−1,j−1) + 1，就是原问题的答案 dfs(i,j)。 所以有 dfs(i,j) = dfs(i−1,j) + dfs(i−1,j−1) + 1 时间复杂度：O(nk)。瓶颈主要在创建数组上。 空间复杂度：O(nk)。 ...
LeetCode 120 https://leetcode.cn/problems/triangle/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ f[i][j] = min(f[i+1][j],f[i+1][j+1]) + triangle[i][j] 时间复杂度：O(n^2)，其中 n 为 triangle 的长度。 空间复杂度：O(n^2)。 ...
LeetCode 516 https://leetcode.cn/problems/longest-palindromic-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 区间 DP，从大区间转移到小区间。f[i][j] 为 s[i] 到 s[j] 的最长回文子序列。 if (s[i] == s[j]) { f[i][j] = 2 + f[i + 1][j - 1]; } else { f[i][j] = max(f[i + 1][j], f[i][j - 1];) } 时间复杂度：O(n^2)，其中 n 为 s 的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的转移个数。本题中状态个数等于 O(n^2)，而单个状态的转移个数为 O(1)，因此时间复杂度为 O(n^2)。 空间复杂度：O(n^2)。 ...
LeetCode 213 https://leetcode.cn/problems/house-robber-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 分类讨论，考虑是否偷 nums[0]： 如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本，调用 198 题的代码解决； 如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本，同样调用 198 题的代码解决。 这两种方案覆盖了所有情况（毕竟 nums[0] 只有偷与不偷，没有第三种选择），所以取两种方案的最大值，即为答案。 时间复杂度：O(n)。其中 n 为 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。为了写起来方便，Python 和 JS 使用了切片（忽略带来的空间），不使用切片的写法请参考其它语言。 ...
LCR 187 https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划。状态转移方程 f[i] = (f[i - 1] + target) % i。 时间复杂度 O(n) ： 状态转移循环 n − 1 次使用 O(n) 时间，状态转移方程计算使用 O(1) 时间； 空间复杂度 O(1) ： 使用常数大小的额外空间； ...