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] 则直观的表示为区别 ij 的最优解。

Example:

这种题目共性就是区间最后求[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位空出来

参考资料

results matching ""

    No results matching ""