动态规划

LeetCode 96 https://leetcode.cn/problems/unique-binary-search-trees/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二叉搜索树的个数为卡特兰数。 \[ C_0 =1 \] \[ C_{n + 1} = \frac{2(2n + 1)}{n + 2}C_n \] ...

NowCoder 311 https://www.nowcoder.com/practice/16409dd00ab24a408ddd0c46e49ddcf8 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ​ 问题分析 ​：圆环有 10 个点（0 到 9），从点 0 出发，每次移动可以到相邻的点（顺时针或逆时针）。要求恰好 n 步后回到点 0 的方法数。 动态规划设置 ​：使用一个数组 curr 来保存当前步数下到达每个点的方案数。初始时，curr[0] = 1，表示 0 步时在原点。 ​ 状态转移 ​：对于每一步，计算下一步到达每个点的方案数。每个点可以从其相邻的两个点转移过来，即 next[j] = curr[left] + curr[right]，其中 left 和 right 是 j 的相邻点。 模数处理 ​：由于结果可能非常大，每次加法后对 MOD 取模。 结果提取 ​：经过 n 步后，curr[0]即为回到原点的方法数。 ...

LCR 126 https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

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) 的空间。 ...