Dynamic Programming

什么情况下可能是动态规划？

满足下面三个条件之一

- Maximum/Minimum
- Yes/No
- Count(*)

则”极有可能“是使用DP

什么情况下可能不是DP

如果题目要求出所有“具体”的方案而不是方案“个数” palindrome partitioning

输入数据是一个“集合”而不是“序列” longest consecutive sequence

4点要素

  1. 状态 State 灵感，创造力，存储小规模问题的结果
  2. 方程 Function 状态之间的联系，怎么通过小的状态，来算大的状态
  3. 初始化 Intialization 最极限的小状态是什么, 起点
  4. 答案 Answer 最大的那个状态是什么，终点

最常见的DP类型

  1. Matrix DP (15%)
  2. Sequence (40%)
  3. Two Sequences DP (40%)
  4. Others (5%)

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 Sequence 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()]

总结

解决动态规划问题的四点要素

- 状态
- 方程
- 初始化
- 答案

三种面试常见的动态规划类别及状态特点

- 矩阵
- 单序列
- 双序列

一些奇技淫巧

- 初始化第一行和第一列
- n个数开n+1个位置的数组