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 124 https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这道题是树形 DP 中的直径 DP。枚举直径拐弯的位置，在每一个拐弯的位置更新答案，将以当前节点为根的链的最大路径和返回给父节点，如果路径和为负数返回 0。 边界条件是空节点的路径和为 0。 需要注意的是，更新答案的是直接的路径和，而返回的是链的路径和。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
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)。 ...
LeetCode 300 https://leetcode.cn/problems/longest-increasing-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题求最长上升子序列（LIS）有两种做法，分别是动态规划和贪心。 ...
LeetCode 53 https://leetcode.cn/problems/maximum-subarray/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题有两种做法，分别是前缀和以及动态规划。 前缀和的做法为维护最小前缀和，答案为当前前缀和减去最小前缀和。 动态规划的转移方程为 \(f[i] = max(f[i-1],0) + nums[i]\)。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...