核心思想

• 自底向上，对应于递归的自上而下
• 状态（数值）转移（一步步）方程（求解）
• 要进行空间优化（减少重复求解次数）
• 使用场景：不要求列出问题的所有解，只要求计算解的数目或找出其中一个最优解

如果说贪心是局部最优，动态规划就是全局最优

通用解法

• 将问题拆分为子问题
  • 什么是子问题：子问题与原问题形式相同或相似，但规模更小
  • 限制：子问题求出的解要记录(选择最优情况)，优化子问题求解次数
  • 求解：使用状态转移方程
• 确定状态
  • 什么是状态：和子问题相关变量的一组取值（为了方便计算存储的数据）
  • 怎么存储：是选择一维还是二维数组还是其他数据结构呢
• 分析边界状态
  • 状态数组的边界部分（推断已知数据填起始值）
• 确定状态转移方程
  • 使用已知的状态（已经存储的数据）求出未知状态（待求解数据）
  • 转移过程：类似于递归
  • 类似时刻的概念，t0 时刻的值 和 t1 时刻的值

• 根据方程遍历

  
  dp.png

状态转移方程 tips

• 每次只消除一个变量，来寻找状态转移方程
• 若无明显确定的初始状态，可全部初始化为某个一般值，并按照某种排序顺序进行递归遍历更新 ( 感觉像数学题，不会就填 012 )
• 若无法形成递推关系，则考虑状态里的变量是不是少了

使用场景

不要求列出问题的所有解，只要求计算解的数目或找出其中一个最优解

看到动态规划，我的第一反应是《运筹学》中的动态规划，然而在众多算法讲解下我关注矛盾点逐渐偏移，还好拽回来了。这俩玩意是一个东西，细节略有不同，相关文章3也讲了这个问题。

运筹学中，如果遇到在某个限制条件下求最优解的问题（如背包问题），则可以使用动态规划。基本概念有6个：

• 阶段（问题划分为多个相互联系的时刻）
• 状态（每个阶段问题的状况）
• 决策（当过程处于某阶段的某状态时，可以做出的不同决定，会影响下一阶段状态）
• 策略（决策按顺序排列的集合，要寻找最优策略）
• 状态转移方程（一个状态到另一个状态的演变过程）
• 指标函数和最优值函数（指标函数：衡量过程优劣的数量指标，如各阶段指标的和或者乘积，最优值函数：指标函数的最优值，min或max）

其强调了策略的概念，结合该点能更快的识别动态规划问题。

---

相关文章

1. 【算法训练营学习笔记-Week05】动态规划其实“名不符实”，动态递推更容易理解
2. 算法基础 - 枚举/递归/动归/深广搜/二分/贪心
3. 五大算法之一-动态规划（从《运筹学》和《算法导论》两个角度分析）