动态规划

动态规划特性

• 重叠子问题
  子问题可能被多次用到，多次计算
• 最优子结构
  最优子结构性质是指问题的最优解包含其子问题的最优解

形式

• 自上而下
  递归实现
• 自下而上
  递推实现

常见类型

• 矩阵型
• 序列型
• 双序列型
• 划分型
• 区间型
• 背包型
• 状态压缩型

• 树型

  
  

实现思路

1. 确定问题状态是什么
   确定最后一步
   划分子问题
2. 状态转移方程是什么
3. 状态的初始值和边界条件是什么
   初始值就是无法用转移方程表示的特殊情况，需要手动定义
   边界条件就是明确计算范围，防止越界

4. 问题要求的最后答案是什么

   
   

使用场景

1. 求最大值/最小值
2. 求可不可行

3. 求方案总数

   
   

参考

如何理解动态规划
动态规划和贪心算法区别