Dynamic Programming

动态规划的4点要素

1 . 状态 State

• 灵感,创造力,存储小规模问题的结果

  • 最优解/Maximum/Minimum

  • Yes/No

  • Count

2 . 方程 Function

• 状态之间的联系,怎么通过小的状态,来求得大的状态

3 . 初始化 Initialization

• 最极限的小状态是什么, 起点

4 . 答案 Answer

• 最大的那个状态是什么,终点

动态规划中的优化

滚动数组优化

f[i] = max(f[i-1], f[i-2] + A[i]);

转换为

f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2])

一维滚动数组优化

这类题目特点

f[i] = max(f[i-1], f[i-2] + A[i]); 由 f[i-1],f[i-2] 来决定状态

可以转化为

f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2]) 由 f[(i-1)%2] 和 f[(i-2)%2] 来决定状态

观察我们需要保留的状态来确定模数

二维动态规划空间优化

这类题目特点

f[i][j] = 由f[i-1]行 来决定状态, 第i行跟 i-1 行之前毫无关系

所以状态转变为

f[i%2][j] = 由f[(i-1)%2]行来决定状态

记忆化搜索

• 本质上: 动态规划

• 动态规划就是解决了重复计算的搜索

• 动态规划的实现方式:

  • 循环(从小到大递推)

  • 记忆化搜索(从大到小搜索)

    • 画搜索树

    • 万金油

什么时候用记忆化搜索?

• 状态转移特别麻烦,不是顺序性。

  • Longest Increasing continuous Subsequence 2D

    • 遍历x,y 上下左右四个格子 dp[x][y] = dp[nx][ny]

  • Coins in a Line III

    • dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1]);

• 初始化状态不是很容易找到

  • Stone Game

    • 初始化dp[i][i] = 0

  • Longest Increasing continuous Subsequence 2D

    • 初始化极小值

• 从大到小

博弈类DP

博弈有先后手

• State

  • 定义一个人的状态

• Function

  • 考虑两个人的状态做状态更新

• Initialize

• Answer

先思考最小状态，然后思考大的状态 -> 往小的状态地推，那么非常适合记忆化搜索

区间类DP

区间类DP特点:

1. 求一段区间的解max/min/count

2. 转移方程通过区间更新

3. 从大到小的更新

区间类DP的做法，是用memorized search，把大区间拆分为小区间来解。而dp[i][j] 则直观的表示为区别 i 到 j 的最优解。

Example:

• Coins in a Line III

• Stone Game

• Burst Balloons

• Scramble String

这种题目共性就是区间最后求[0,n-1] 这样一个区间。 逆向思维分析 从大到小就能迎刃而解。

逆向 =>> 分治类似

划分类DP

Reference: https://mnmunknown.gitbooks.io/algorithm-notes/626,_dong_tai_gui_hua_ff0c_subarray_lei.html

“划分类” DP，是指给定原数组之后，将其划分为 k 个子数组，使其 sum / product 最大 / 最小的 DP 类问题。

这类问题的 optimal substructure 是，对于给定区间的globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾” 来保证 local 子问题之间的连续性；用 global 来记录最优解之间可能的不连续性。

划分类DP 与 区间类DP 主要区别在于，我们只取其中 k 段，而中间部分可以留空；而区间类 DP 子问题之间是连贯而不留空的。区间类 DP 是记忆化的 divide & conquer, 划分类 DP 则是不连续 subarray 的组合，不同于区间类 DP 每一个区间都要考虑与计算，划分类DP 很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的 local / global 结构来保证算法的正确性。

背包类DP

背包类DP 特点:

1. 用值作为DP维度

2. DP过程就是填写矩阵

3. 可以滚动数组优化

其他

何时可能使用DP

• 求最大最小值 max/min

• 求能否达到 yes/no

• 求数量 count(*)

编程小技巧

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

参考资料

• Hawstein: 动态规划：从新手到专家

• 什么是动态规划？动态规划的意义是什么?