🧗 动态规划
DP 五步法 · 背包/子序列/编辑距离 · 贪心与回溯的取舍
1. 动态规划的解题五步？（套模板破题）
- 定义 dp 数组：dp[i] 表示什么（明确下标含义）
- 找状态转移方程：dp[i] 如何由更小的状态推出（核心）
- 初始化：dp[0]/dp[1] 等边界值
- 确定遍历顺序：从前到后/从后到前、单层/双层循环
- 验证：拿小例子手算对照 dp 表
什么时候用 DP：最优子结构（子问题最优→全局最优）+ 重叠子问题（子问题重复计算）。对比递归：递归 + 备忘录（记忆化搜索）是自顶向下版 DP，等价。
爬楼梯：最简 DP 入门
// 每次爬 1 或 2 阶，到 n 阶有几种方法
// dp[i] = dp[i-1] + dp[i-2]（斐波那契变体）
public int climbStairs(int n) {
int a = 1, b = 2; // dp[1]=1, dp[2]=2
for (int i = 3; i <= n; i++) {
int c = a + b; // 滚动变量省数组
a = b; b = c;
}
return n <= 2 ? n : b;
}🎯 面试要点
- 很多 dp 可以滚动数组优化空间（O(n) → O(1)），面试主动提是加分项
- 先写二维 dp 再考虑压缩，别一上来就写滚动（易错）
- 能递归的题大多能 DP；"记忆化搜索"代码结构更接近题意，可以先给这个再优化
2. 01 背包和完全背包？
- 01 背包：每件物品只能选一次。
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])。一维优化时容量倒序遍历（保证每件只用一次） - 完全背包：每件物品无限次。一维时容量正序遍历（可重复取）
01 背包一维写法（背模板）
// 容量 W，n 件物品（重量 w[i]、价值 v[i]），求最大价值
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
for (int c = W; c >= w[i]; c--) // 倒序：每个物品只能用一次
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
return dp[W];
// 完全背包：把内层改成正序 for (c = w[i]; c <= W; c++)
// 变体：凑满 W 的方案数 → dp[0]=1，dp[c] += dp[c-w[i]]🎯 面试要点
- 常见变体：分割等和子集（01 背包：dp 判断能否凑满 sum/2）、零钱兑换（完全背包最少硬币）、组合总和 IV（排列 vs 组合——外层循环物品种类 vs 容量）
- 先答"二维 + 转移方程"，再展示一维优化——展示思考过程
3. 子序列类 DP：LIS 和 LCS？
- 最长递增子序列（LIS）：dp[i] = 以 i 结尾的最长递增子序列长度，转移 O(n²)；优化：贪心 + 二分（patience sorting，维护递增序列）O(n log n)
- 最长公共子序列（LCS）：dp[i][j] = 两串前 i/j 的 LCS 长度；字符相同 dp[i][j]=dp[i-1][j-1]+1，否则取 max(上, 左)
- 其他高频：最长回文子串/子序列（区间 DP，dp[i][j] 表示 [i,j] 区间）、编辑距离
最长公共子序列
public int lcs(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = a.charAt(i-1) == b.charAt(j-1)
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}🎯 面试要点
- 回文类题 dp 填表顺序特殊：从 i 大到小（依赖左下角），或按区间长度遍历
- 编辑距离（最少操作把 a 变 b）= LCS 的近亲：dp[i][j] 三种操作（删/插/换）取最小
- 子序列 vs 子串：子串要求连续，用滑动窗口/双指针往往更简单
4. 贪心、DP、回溯怎么选？
- 贪心：每一步局部最优 = 全局最优（需证明）。代表题：跳跃游戏、加油站、区间调度、硬币（部分面额下贪心成立）。贪心能过的题一定可以 DP，但贪心 O(n) 更快
- 回溯：穷举 + 剪枝，找所有解（组合/排列/子集）。代表题：全排列、组合总和、N 皇后、括号生成。模板：
做选择 → 递归 → 撤销选择（DFS + 回溯） - 判断：求"最值/方案数" → DP 或贪心；求"所有方案/列举" → 回溯；数据量大且状态多维 → DP 空间可能不够，考虑贪心或贪心+DP
回溯模板（全排列）
List<List<Integer>> res = new ArrayList<>();
int n = nums.length; // 先取长度
boolean[] used = new boolean[n];
void backtrack(int[] nums, List<Integer> path) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 剪枝
used[i] = true;
path.add(nums[i]);
backtrack(nums, path); // 递归
path.remove(path.size() - 1); // 撤销选择
used[i] = false;
}
}🎯 面试要点
- 回溯复杂度通常指数级，必须先讲"剪枝"再写代码（排序去重、used 数组、start 下标）
- 组合/子集用 start 下标避免回头；排列用 used 数组
- 贪心题面试喜欢让你"证明正确性"：反例论证是核心