动态规划

核心思想 (Core Philosophy)

• 定义：将待求解问题分解成若干个重叠子问题，通过保存子问题的解（备忘录）来避免重复计算。
• 与分治法的区别：
  • 分治法：子问题相互独立（如归并排序）。
  • 动态规划：子问题重叠（如斐波那契数列）。
• 基本要素 (必考概念)：
  1. 最优子结构：问题的最优解包含其子问题的最优解。
  2. 重叠子问题：递归求解时，相同的子问题被反复计算。
  3. 无后效性：某阶段的状态一旦确定，就不受后续决策影响（“未来与过去无关”）。

基础

• 解题步骤：
  1. 刻画结构：找出最优解的性质，刻画其结构特征。
  2. 定义方程：递归地定义最优值（写出状态转移方程）。
  3. 计算最优值：通常采用自底向上的方式计算（填表）。
  4. 构造最优解：根据计算过程中的记录，追溯构造出解（如果需要具体方案）。