🧮 动态规划
将问题拆解为重叠子问题，通过记忆化或自底向上的方式避免重复计算，是算法面试最重要的专题之一。
10 题 · 简单 ×2 中等 ×7 困难 ×1
| # | 题目 | 难度 |
|---|---|---|
| 70 | 爬楼梯 | 简单 |
| 118 | 杨辉三角 | 简单 |
| 198 | 打家劫舍 | 中等 |
| 279 | 完全平方数 | 中等 |
| 322 | 零钱兑换 | 中等 |
| 139 | 单词拆分 | 中等 |
| 300 | 最长递增子序列 | 中等 |
| 152 | 乘积最大子数组 | 中等 |
| 416 | 分割等和子集 | 中等 |
| 32 | 最长有效括号 | 困难 |
核心思路
- 爬楼梯：
dp[i] = dp[i-1] + dp[i-2]，斐波那契数列。 - 打家劫舍：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])，相邻不可同时选。 - 零钱兑换 /
完全平方数：完全背包，
dp[i] = min(dp[i], dp[i-coin] + 1)。 - 最长递增子序列：
dp[i]= 以nums[i]结尾的 LIS 长度；也可用二分 + 贪心 O(n log n)。 - 乘积最大子数组：同时维护当前最大值和最小值（负负得正），
maxDP[i] = max(nums[i], maxDP[i-1]*nums[i], minDP[i-1]*nums[i])。 - 分割等和子集：01 背包，目标为
sum/2，dp[j] = dp[j] || dp[j - nums[i]]。 - 最长有效括号：
dp[i]表示以s[i]结尾的最长有效括号长度；遇到)时查看配对的(前的状态。