> For the complete documentation index, see [llms.txt](https://luj.gitbook.io/code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luj.gitbook.io/code/dynamic-programming.md).
# Dynamic Programming
*Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.*
## ***Overlapping Subproblems***
* *When solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed.*
## ***Optimal Substructure***
* *A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.*
### 动态规划四要素
**状态 State**
* 灵感，创造力，存储小规模问题的结果
* 最优解/Maximum/Minimum
* Yes/No 存在不存在满足条件的答案
* Count(\*) 有多少个可行解
**方程 Function**
* 状态之间的联系，怎么通过小的状态，来求得大的状态
**初始化 Intialization**
* 最极限的小状态是什么, 起点
**答案 Answer**
* 最大的那个状态是什么，终点
### 状态的六大问题:
1. 坐标型15%
```
jump game: 棋盘，格子
f[i]代表从起点走到i坐标
```
2. 序列型30%
```
f[i]代表前i个元素总和，i=0表示不取任何元素
```
3. 双序列型30%
4. 划分型10%
5. 背包型10%
6. 区间型5%
### 滚动数组优化
```
f[i] = max(f[i-1], f[i-2] + A[i]);
```
转换为
```
f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2])
```
### 记忆化搜索
记忆搜索本质是：动态规划
* 动态规划就是解决了重复计算的搜索
动态规划的实现方式：
* 循环（从小到大递推）
* 记忆化搜索(从大到小搜索)
记忆化搜索
* 画搜索树
* 万金油搜索可以解决一切问题
* 记忆化搜索可以解决一切动态规划的问题，动态规划都可以用记忆化搜索解决， 但是记忆化搜索不一定是最优解
### 什么时候用记忆化搜索呢?
1. 状态转移特别麻烦, 不是顺序性
2. 初始化状态不是特别容易找到
这时候我们用万能的dfs加memorization\
#### 那怎么根据DP四要素转化为记忆化搜索呢？
**State**:
* dp\[x]\[y] 以x,y作为结尾的最长子序列
**Function**:
* 遍历x,y 上下左右四个格子
```
dp[x][y] = dp[nx][ny] + 1
(if a[x][y] > a[nx][ny])
```
**Initialize**:
* dp\[x]\[y] 是极小值时，初始化为1
**Answer**:
* dp\[x]\[y]中最大值
