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 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 使用了切片（忽略带来的空间），不使用切片的写法请参考其它语言。 ...
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)。 ...
LeetCode 70 https://leetcode.cn/problems/climbing-stairs/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 斐波那契数列。f[i] = f[i - 1] + f[i - 2]。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...
LeetCode 32 https://leetcode.cn/problems/longest-valid-parentheses/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是一道一维 DP 的题目。f[i] 表示以 i 结尾的最长有效括号的长度。由于有效括号只会以 ‘)’ 结尾，所以只在当前字符为 ‘)’ 时的状态转移。 当前一个字符为 ‘(’ 时，转移到 f[i] = f[i - 2] + 2。 当第 i - f[i - 1] - 1 个字符为 ‘(’ 时，将原本不连续的两段长度合并，即转移到 f[i] = f[i - 1] + f[i - f[i - 1] - 2] + 2。 时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。 空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。 ...
LeetCode 1143 https://leetcode.cn/problems/longest-common-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ LCS 线性 DP 问题，状态转移方程如下： if (s[i] == t[j]) { f[i + 1][j + 1] = f[i][j] + 1; } else { f[i + 1][j + 1] = max(f[i + 1][j], f[i][j + 1]); } 时间复杂度：O(nm)。 空间复杂度：O(nm)。 ...
LeetCode 72 https://leetcode.cn/problems/edit-distance/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这是线性 DP 的经典题目，类似 LeetCode 1143 最长公共子序列。 状态转移方程为： //word1[i] == word2[j] f[i + 1][j + 1] = f[i][j]; //word1[i] != word2[j] f[i + 1][j + 1] = min({f[i + 1][j], f[i][j + 1], f[i][j]}) + 1; 在不相等时，三种情况分别对应插入，删除，替换的情况。 此外，还要注意数组的初始化操作。 f[i + 1][0] = i + 1; f[0][j + 1] = j + 1; 时间复杂度：O(nm)，其中 n 为 word1 的长度，m 为 word2 的长度。 空间复杂度：O(nm)。 ...