Dynamic Programming

动态规划的4点要素

  1. 状态 State 灵感，创造力，存储小规模问题的结果
  2. 方程 Function 状态之间的联系，怎么通过小的状态，来算大的状态
  3. 初始化 Intialization 最极限的小状态是什么, 起点
  4. 答案 Answer 最大的那个状态是什么，终点

常见的四种DP类型

  • Sequence DP
  • 2 Sequence DP
  • Matrix DP
  • Others
    • 背包类
    • 区间类

什么情况下可能使用DP

  • 求 max/min
  • yes/no 求能否达到
  • count(*) 求数量

注意点

  • 多开一位，把0位空出来

Reference