第三章：动态规划 (Dynamic Programming)

一、 核心概念与设计思想

• 核心逻辑：将复杂问题分解为重叠子问题，通过填表记录子问题的解，避免重复计算，将指数复杂度降为多项式复杂度。
  
• 适用场景：求解最值问题（最大/最小）、方案计数、可行性判断。

---

二、 三大理论基石（必考定义与证明）

判断问题能否用动态规划解决，必须满足以下三个性质：

1. 最优子结构 (Optimal Substructure)

• 定义：问题的最优解包含其子问题的最优解。
  
• 证明方法：反证法（剪切-粘贴法），步骤如下：
  1. 假设原问题存在一个最优解 。
     
  2. 该解将问题划分为子问题 ，对应解为 。
     
  3. 反证假设：假设存在 是 的更优解。
     
  4. 构造新解：用 替换 ，得到新解 。
     
  5. 导出矛盾：由于 更优， 的总代价应优于 ，这与 是最优解矛盾。
     
  6. 结论：假设不成立， 必然是子问题的最优解。

2. 无后效性 (No After-effect)

• 定义：状态确定后，后续决策不会影响该状态。
  
• 通俗理解：“未来不影响历史”。计算当前状态时，只需已知前置状态的结果值，无需知道其具体决策路径。

3. 重叠子问题 (Overlapping Subproblems)

• 定义：递归求解时，相同的子问题被重复计算多次。
  
• 关键作用：这是动态规划能提升效率的根本原因，通过记忆化存储避免重复计算。

---

三、 经典线性模型详解

状态通常定义为 dp[i]，表示考虑前 i 个元素时的最优解。

1. 最大子段和 (Maximum Subarray Sum)

• 问题：给定序列 ，求最大连续子序列和。
  
• 状态定义： 表示以第 个元素结尾的最大子段和。
  
• 状态转移：
  
  
• 核心思想：
  • 若 ，则累加（继承资产）
    
  • 若 ，则舍弃（另起炉灶）
    
• 最终答案：。

2. 0/1 背包问题

• 问题： 个物品，容量 ，每个物品只能选一次。
  
• 状态定义： 表示前 个物品、容量为 时的最大价值。
  
• 状态转移：
  
  
• 空间优化（滚动数组）：
  c for (int i = 1; i <= n; i++) for (int r = W; r >= w[i]; r--) // 必须逆序！ dp[r] = max(dp[r], dp[r-w[i]] + v[i]);
  
• 逆序原因：确保计算时使用的是上一层状态，防止物品被重复选取。

3. 完全背包问题

• 问题：每个物品可选无限次。
  
• 状态转移：
  
  
• 空间优化：
  c for (int i = 1; i <= n; i++) for (int r = w[i]; r <= W; r++) // 必须顺序！ dp[r] = max(dp[r], dp[r-w[i]] + v[i]);
  
• 顺序原因：允许使用当前层已更新状态，实现物品的多次选取。

---

四、 区间模型详解

状态通常定义为 dp[i][j]，表示区间 的最优解，通过枚举分割点 合并子问题。

矩阵连乘问题

• 问题：给定 个矩阵链 ，求最少乘法次数。
  
• 状态定义： 表示计算 的最少乘法次数。
  
• 状态转移：
  
  • ：分割点
    
  • 的维度为
    
• 填表顺序（关键）：
  • 必须按链长（len） 递增的顺序计算（长度从 2 到 ）。
    
  • 原因：计算大区间时需要其内部小区间已全部求解。
    
• 复杂度：时间 ，空间 。

---

五、 复习要点总结

1. 掌握一套证明方法

• 熟练运用 “剪切-粘贴”反证法 证明最优子结构。

2. 区分两类背包问题

• 0/1背包：物品唯一，空间优化需逆序循环。
  
• 完全背包：物品无限，空间优化需顺序循环。

3. 掌握三类经典模型

• 线性模型（如最大子段和）：状态递推，关注继承或舍弃的抉择。
  
• 背包模型：状态为二维（可优化为一维），关注物品选择与容量限制。
  
• 区间模型（如矩阵连乘）：状态为二维，关注分割点枚举与合并代价。

4. 理解两个关键顺序

• 0/1背包逆序 vs 完全背包顺序：由物品选取限制决定。
  
• 区间DP按长度递增：由状态依赖关系决定。

---

本章核心：动态规划通过状态定义和状态转移方程将问题结构化，利用记忆化避免重叠子问题的重复计算。重点在于识别问题模型、设计正确的状态表示、并保证计算顺序符合状态间的依赖关系。