Dynamic Programming

VS Divide and Conquer

• 利用已经计算的结果，解决了重复计算的搜索，是D&C的优化

实现方式

多重循环

• 正规，容易理解接受，存储了所有的空间结果
• 消耗了大量空间，存在空间优化的可能性
• 思考有难度
• 四个要素
  • state：存储最小规模问题的结果
  • initialization：最极限的小状态是什么，起点
  • function：通项公式，如何从小状态来计算大状态
  • answer：最终状态
• 构建function
  • 从基础结构开始考虑起，i = 0, 1, 2, 3以便发现规律

记忆化搜索

• 容易从搜索算法直接转化过来
• 有时可能可以节省更多的时间
• 递归

When

• 极有可能
  • 求max/min
  • 判断是否可行
  • 统计方案个数
• 极不可能
  • 求出所有的具体方案，而非个数
  • 输入是一个集合，而不是序列，（可以排序或者交换）
  • 暴力算法已经是多项式级别
    • 动归擅长优化2^n, n!到n^2,n^3
    • 不擅长优化n^3到n^2

类型

坐标型 10%

state: f[x]/f[x][y] 从起点走到坐标x/x,y function: 走到x,y点的前一步 initialize:

• 对于2D matrix,初始化[x][0], [0][y]，即第0行，第0列,尤其对于function中有-1的情况 answer:

接龙型 20%

state: function: initialize: answer:

划分型 20%

state: function: initialize: answer:

匹配型 20%

state: function: initialize: answer:

背包型 20%

state: function: initialize: answer:

区间型 10%

state: function: initialize: answer: