#Dynamic Programming
###State 状态定义 储存小规模问题的结果 ###Function 初始化,终点先有值 状态只加的联系,怎么通过小的状态来算大的状态 ###Initialize 循环递推求解 最极限的小状态是什么 ###Answer 求结果:起点 最大的那个状态是什么
###一般什么情况下可能是动态规划
- 求Maximum/Minimum
- Yes/No
- Count
###一般什么情况下不是动态规划
- 求所有具体的方案而不是方案数
- 输入数据是一个集合而不是序列
###常见DP ####Matrix DP
- state: f[x][y] 表示我从起点走到坐标x,y......
- function: 研究走到x,y这个点之前的一步
- intialize: 起点
- answer: 终点
####Sequence Dp
- state: f[i]表示“前i”个位置/数字/字母,(以第i个为)...
- function: f[i] = f[j] ... j 是i之前的一个位置
- intialize: f[0]..
- answer: f[n-1]..
####Two Sequences Dp
- state: f[i][j]代表了第一个sequence的前i个数字 /字符 配上第二个sequence的前j个...
- function: f[i][j] = 研究第i个和第j个的匹配关系
- intialize: f[i][0] 和 f[0][i]
- answer: f[s1.length()][s2.length()]