动态规划（Dynamic Programming，DP）是一种把大问题拆成小问题、记住小问题答案、用表格或记忆化避免重复计算的方法，常用于最优值与计数类题目。
何时用 DP
-
存在最优子结构：整体最优由若干子问题的最优组成。
-
存在重叠子问题：相同子问题会被多次用到。
-
无后效性：状态一旦确定，不再依赖未来选择。
三种写法
-
自顶向下：DFS + 记忆化/备忘录（memo），写起来直观。
-
自底向上：填表（tabulation），顺序可控、常更快。
-
状态压缩：在不丢信息的前提下减少维度/空间（如滚动数组、位压缩）。
设计五步法
-
状态定义： f[索引,约束] 表示的含义要说清楚。
-
转移方程：从哪些子状态来，取max/min/sum？
-
边界初始化：起点值、不可达用 - \infin 或 0 。
-
遍历顺序：保证用到的子状态已计算好（如背包容量要倒序）。
-
答案位置：是f[N]、f[N][W] 还是整张表的最值？