# 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](dynamic_programming/coins_in_a_line_iii)
* [Stone Game](dynamic_programming/stone_game)
* [Burst Balloons](dynamic_programming/burst-balloons)
* Scramble String

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

逆向 =>> 分治类似

## 划分类DP

Reference: [https://mnmunknown.gitbooks.io/algorithm-notes/626,\_dong\_tai\_gui\_hua\_ff0c\_subarray\_lei.html](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&#x20;
* 求数量 count(\*)&#x20;

### 编程小技巧

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

## 参考资料

* [Hawstein: 动态规划：从新手到专家](http://www.hawstein.com/posts/dp-novice-to-advanced.html)
* [什么是动态规划？动态规划的意义是什么?](https://www.zhihu.com/question/23995189)
