Appearance
动态规划与贪心
动态规划：先定义状态，再写转移
动态规划适用于有重叠子问题和最优子结构的问题。写题顺序：
- 定义
dp状态：下标、含义、单位； - 写出状态转移，说明每个分支代表什么选择；
- 初始化最小规模状态；
- 确认遍历顺序保证依赖状态已计算；
- 用边界输入验证，并判断是否可滚动压缩空间。
不要只背公式。dp[i] 可能代表“以 i 结尾的最优值”，也可能代表“前 i 个元素的全局最优值”；二者的答案位置和转移不同。
一维序列
cpp
// 最大子数组和：best_end 表示必须以当前元素结尾的最大和。
int best_end = nums.front();
int answer = best_end;
for (std::size_t i = 1; i < nums.size(); ++i) {
best_end = std::max(nums[i], best_end + nums[i]);
answer = std::max(answer, best_end);
}斐波那契、爬楼梯、打家劫舍等常只依赖有限前项，可把 O(n) DP 数组压缩为常数变量。应先处理空数组和极小长度。
0/1 背包与完全背包
令 dp[capacity] 表示当前处理到的物品能取得的最优值：
cpp
// 0/1 背包：每件最多一次，容量必须倒序。
for (int item = 0; item < n; ++item)
for (int cap = capacity; cap >= weight[item]; --cap)
dp[cap] = std::max(dp[cap], dp[cap - weight[item]] + value[item]);
// 完全背包：每件可重复，容量正序。
for (int item = 0; item < n; ++item)
for (int cap = weight[item]; cap <= capacity; ++cap)
dp[cap] = std::max(dp[cap], dp[cap - weight[item]] + value[item]);循环方向控制是否会在同一轮复用当前物品。计数问题还要区分：先枚举物品通常统计组合，先枚举容量再枚举物品通常统计排列；具体以题目是否区分顺序为准。
求最小值时将不可达状态初始化为足够大的 INF，并在转移前确认前置状态可达；求方案数时留意 long long 或取模，不能用溢出后的 int 当逻辑状态。
双序列、区间与树形 DP
- LCS：
dp[i][j]表示两个前缀的最长公共子序列；字符相等取左上加一，否则取上/左最大； - 编辑距离：字符不同对应替换、删除、插入三种前置状态中的最小值加一；首行首列初始化为与空串互转的操作数；
- 回文区间：常用
dp[left][right]，需要先算更短内部区间，所以left通常倒序或按区间长度枚举； - 区间 DP：如戳气球，枚举区间与“最后执行”的分割点；
- 股票状态机：将“第几天、剩余交易次数、是否持有”作为状态，先定义交易次数在买入还是卖出时消耗，避免下标混乱；
- 树形 DP：后序返回每个节点的有限状态，让父节点合并子节点结果。
贪心：需要可证明的局部选择
贪心不是“每步看起来最好”就成立，而是必须能用交换论证、保持领先或不变量证明局部选择不会损失全局最优。
常见可靠模式：
| 问题 | 贪心选择 |
|---|---|
| 选择最多不重叠区间 | 总是选结束时间最早的可选区间 |
| 跳跃游戏 I | 扫描时维护目前可达的最远下标 |
| 跳跃游戏 II | 在当前可达区间内维护下一跳最远边界 |
| 分发饼干 | 两边排序，用最小可满足饼干匹配最小未满足需求 |
| 分发糖果 | 左右各扫描一次，逐位置取两侧约束最大值 |
| 划分字母区间 | 预处理每字符最后出现位置，扫描维护当前段最远边界 |
区间贪心大多需要排序，但排序键由证明决定：求最多不重叠通常按结束时间，合并区间通常按开始时间。不要看到区间就统一套同一种排序。
如何选择：DP、贪心还是搜索
text
要求所有方案 / 约束组合 → 回溯、状态压缩或 DP
存在可证明的局部最优规则 → 贪心
最优值由多个历史状态决定 → DP
有序或答案空间单调 → 二分
图上的可达性 / 连通块 / 最短层数 → DFS、BFS、并查集面试表达建议：先说状态或不变量，再给转移/选择理由、复杂度、边界条件，最后说明空间优化是否必要。这样比只报出题号或模板更能展示可迁移的解题能力。