动态规划

STATE · TRANSITION · MEMOIZATION

DP 问题特性

最优子结构

问题的最优解包含子问题的最优解。全局最优可由局部最优递推得到。

重叠子问题

递归时同一子问题被重复计算。用表格（或记忆化）保存结果，避免重复。

无后效性

未来决策只依赖当前状态，与如何到达当前状态无关。

DP 解题思路

  1. 定义状态：用 dp[i] 或 dp[i][j] 表示子问题的解（如「前 i 个物品、容量 w 下的最大价值」）。
  2. 状态转移方程：写出 dp 当前状态如何由已求子状态推导。
  3. 边界条件：确定初始值（如 dp[0]=0、第一行/列）。
  4. 计算顺序：按依赖关系确定填表顺序（自底向上或按拓扑序）。

0-1 背包

n 件物品，每件有重量 w 和价值 v，背包容量 W。每件物品最多选一次。求最大价值。 

dp[i][w] = 前 i 件物品、容量 w 下的最大价值
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]]+val[i-1])  // 不选 or 选
边界: dp[0][*]=0, dp[*][0]=0