动态规划入门：状态、转移与背包

一句话定义

动态规划（Dynamic Programming, DP）把问题分解为重叠的子问题，用「状态定义 + 转移方程 + 初始化 + 计算顺序」四步把指数级的重复计算压成多项式；最优子结构保证局部最优拼成全局最优。

为什么重要

DP 是算法设计的最大杠杆：从爬楼梯到编辑距离、从背包到序列比对（生物信息），一切「看起来只能枚举」的问题都常被 DP 摘下来。它与分治的唯一差别（重叠子问题）与贪心的分界线（有无贪心选择性质）是算法思想的骨架；掌握四步法后，你面对新题的反应从「背过吗」变成「状态怎么定」。

前置知识

kp-024（分治——DP 是其「子问题共享结果」的变体）；递归与记忆化写法。

核心概念

• 两大前提：重叠子问题（直接递归会大量重复计算）+ 最优子结构（最优解由子问题最优解构成）。
• 两种形态：自顶向下记忆化（memoization，按需算）与自底向上递推（tabulation，按序填表）；等价，后者常数小且便于空间优化。
• 四步法：①状态（用最少的参数唯一刻画子问题）②转移（f(状态) 如何由更小状态组合）③初始化（边界状态）④遍历顺序（保证算 f(s) 时依赖项已就绪）。
• 经典起点：爬楼梯/斐波那契 → 打家劫舍（不相邻最大和）→ 0/1 背包 → 完全背包 → LCS → 编辑距离。
• 空间优化（滚动数组）：若 f(i) 只依赖 f(i−1) 层，可把二维压一维；0/1 背包一维化必须倒序容量（防止本层物品被重复选取）。
• 复杂度：状态数 × 每状态转移代价，如背包 Θ(n·W)。

直观类比

爬楼梯只依赖前两级台阶：直接递归是「每次都重新往下数」，记忆化是「每级台阶记个纸条」，递推是「从第一级往上边走边写」。0/1 背包倒序更新则是「一排格子从右往左刷漆，保证刷到每格时看到的是上一行的旧漆」。

原理与机制

0/1 背包四步法全程示范：

状态:  dp[i][w] = 前 i 件物品、容量 w 下的最大价值
转移:  dp[i][w] = max( dp[i−1][w],                    // 不选第 i 件
                      dp[i−1][w−wᵢ] + vᵢ )            // 选（需 w ≥ wᵢ）
初始化: dp[0][*] = 0（无物品价值 0）
顺序:  i 从 1..n，w 从 0..W
空间优化: 一维 dp[w]，w 从 W 倒序到 wᵢ——
          倒序保证读取的 dp[w−wᵢ] 还是「上一行」，每件物品只被选一次。
完全背包（每件无限件）: 改为 w 正序——正序读取的已是「本行」，
          允许同一物品多次计入。
复杂度: Θ(nW) 时间；一维后 Θ(W) 空间。

记忆化对照（爬楼梯）：

函数 f(k):            // 到第 k 级的方案数
    若 k ≤ 1: 返回 1
    返回 f(k−1) + f(k−2)      // 加 memo[k] 缓存后 Θ(n)
无记忆化的直接递归是 Θ(φⁿ)，重叠子问题在这里看得最清楚。

图示

0/1 背包一维滚动更新的方向:
容量 →  0  1  2  3  4  5
第i层   [0, 0, 0, 0, 0, 0]      ← 初始
倒序刷:        从 W 到 wᵢ，dp[w] = max(dp[w], dp[w−wᵢ]+vᵢ)
               （右侧已刷=本层新值，左侧未刷=上一层旧值 ⇒ 不重复选取）
若正序: dp[w−wᵢ] 已是本层 ⇒ 同一物品可被计入多次 ⇒ 变成完全背包。

实例或案例

• 打家劫舍：dp[i] = max(dp[i−1], dp[i−2] + a[i])——一维线性 DP 模板。
• 最长公共子序列 LCS：dp[i][j] = a[i]==b[j] ? dp[i−1][j−1]+1 : max(dp[i−1][j], dp[i][j−1])，Θ(nm)。
• 硬币找零（币值 {1,3,4} 凑 6）：完全背包，dp[w]=min(dp[w], dp[w−c]+1)，恰好修正 kp-025 的贪心反例（2 枚）。
• 编辑距离、最长递增子序列（O(n²) DP → 贪心+二分 O(n log n)）是后续进阶入口。

常见误区

• 无重叠子问题仍写 DP：徒增代码复杂度（分治已够）。
• 状态定义遗漏关键参数（如背包忘了容量维度）：转移拼不回来，越定义越乱；状态要「足够描述未来决策所需的一切」。
• 一维化背包不倒序：把 0/1 背包悄悄变成完全背包，结果偏大。
• 初始化错一格（dp[0] 语义）：整表带病传播；初始化就是「边界状态的定义」，不可敷衍。
• 把「贪心能解」的题写 DP：不是错但慢；先试交换论证（kp-025），失败再 DP。

自测题

1. 写出爬楼梯（每次 1 或 2 步）的状态与转移，并把空间压到 O(1)。

答案要点：f(i)=f(i−1)+f(i−2)，f(0)=f(1)=1；只留两个变量滚动，Θ(n) 时间 O(1) 空间。

1. 解释 0/1 背包一维化必须倒序、完全背包必须正序的原因。

答案要点：倒序保证依赖项仍是上一层（每件最多选一次）；正序则依赖本层新值（同件可重复选），方向即语义。

1. 用四步法描述「数组最大子段和」的 DP 解并比较分治解。

答案要点：状态 dp[i]=以 i 结尾的最大和，转移 dp[i]=max(a[i], dp[i−1]+a[i])，答案取 max dp；Θ(n) 优于分治 Θ(n log n)——识别「线性依赖」可免去分治。

与其他知识点的关系

kp-024 提供对照（独立 vs 重叠）；kp-025 划界（贪心证不出时来 DP）；kp-028 扩展区间/状压/树形；kp-017 的 Floyd 也是一张 DP 表；kp-027 回溯常被误当 DP 用在「求所有解」场景。

延伸阅读

《算法导论》第 14 章（装配线、LCS、最优二叉搜索树）；《算法竞赛入门经典》DP 章节；LeetCode 70/198/416 作为入门三连。