动态规划

定义

Dynamic programming, 简称 DP，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解决一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定的子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

适用情况

1. 最优子结构性质
   • 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
     2. 无后效性
   • 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
2. 子问题重叠性质
   • 是指用递归算法自顶向下对问题求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查一下结果，从而获得较高的效率。

动态规划关键点

1. 最优子结构
   • Opt[n] = best_of(opt[n-1], opt[n-2], ...)
2. 储存中间状态
   • opt[i]
3. 递推公式（状态转移方程或者 DP 方程）
   • Fib: opt[I] = opt[n-1] + opt[n-2]
   • 二维路径: opr[i, j] = opt[i+1][j] + opt[i][j+1]（且判断 a[i, j] 是否空地）

对应老师在实战解析写的三步：

1. 重复性（分治）
2. 定义状态数组
3. DP 方程