动态规划笔记

• 递归、递推

  递归 自顶向下

  递推 自底向上

• 动态规划题的一般思路

  • 先写出递归思路
  • 然后剪枝(前面二者都是自上而下)
  • 然后写出dp(不同于剪枝的是 dp是自底向上)

dp问题核心是穷举，dp特点是存在 重叠子问题 最优子结构

然后只要在此基础上列出 状态转移方程 即可

动态规划的三要素：

• 重叠子问题
• 最优子结构
• 状态转移方程

思维框架：

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。