什么情况下使用动态规划
满足下面三个条件之一，则极有可能使用动态规划 90% - 95%：
求最大值，最小值
判断是否可行
统计方案个数
极不可能使用动态规划的情况：
求出所有具体的方案而非方案的个数
输入数据是一个集合而不是序列
暴力的算法已经是多项式级别
动态规划的 4 点要素
状态 State
灵感，创造⼒，存储小规模问题的结果
最优解 / Maximum / Minimum
Yes / No
Count(*)
方程 Function
状态之间的联系，怎么通过⼩的状态，来求得⼤的状态
初始化 Intialization
最极限的小状态是什么，起点
答案 Answer
最⼤的那个状态是什么，终点
总结
什么情况下可能使用/不用动态规划?
最大值最小值/是否可行/方案总数
求所有方案/集合而不是序列/指数级到多项式
三种面试常见的动态规划类别及状态特点
坐标,单序列,双序列
两招独孤九剑
二维DP需要初始化第0行和第0列
n个字符的字符串要开n+1个位置的数组
坐标型
state:
f[x] 表示我从起点走到坐标x……
f[x][y] 表示我从起点走到坐标x,y……
function: 研究走到x,y这个点之前的一步
initialize: 起点
answer: 终点
单序列
以字符串居多
state: f[i]表示前i个位置/数字/字符,第i个…
function: f[i] = f[j] … j 是i之前的一个位置
initialize: f[0]..
answer: f[n]..
一般answer是f(n)而不是f(n-1), 因为对于n个字符,包含前0个字符(空串),前1个字符……前n个字符。
双序列
一般给两个字符串
state: f[i][j]代表了第一个sequence的前i个数字/字符,配上第二个sequence的前j个…
function: f[i][j] = 研究第i个和第j个的匹配关系
initialize: f[i][0] 和 f[0][i]
answer: f[n][m]
n = s1.length()
m = s2.length()
划分型
题目：给一个序列，求一次划分区间，求区间中的最大值
state: f[i] 表⽰示前 个元素的最⼤大值
function: f[i] = 前 i 个元素里⾯选一个区间的最⼤值
initialize: f[0]..
answer: f[n-1]..
优化
state:
gobal[i] 表示前 i 个元素的最大值
local[i] 表⽰示包含第 i 个元素前 i 个元素的最大值
function:
global[i] = 通过 local[i] 更新
local[i] = 通过原序列或者 global[i] 更新
initialize: global[0].. Local[i]
answer: global[n-1]..
背包型
特点：
用值作为DP维度
DP过程就是填写矩阵
可以滚动数组优化
Backpack
State:
f[i][S] “前i”个物品，取出一些能否组成和为S
Function:
f[i][S] = f[i-1][S - a[i]] or f[i-1][S]
Intialize:
f[i][0] = true; f[0][1..target] = false
Answer:
检查所有的f[n][j]
时间复杂度 O(n*S) ， 滚动数组优化
区间型
特点：
求一段区间的解max/min/count
转移方程通过区间更新
从大到小的更新
这种题目共性就是区间最后求[0,n-1] 这样一个区间
逆向思维分析 从大到小就能迎刃而解
逆向 =》 分治类似
博弈型
博弈有先后手
State:
定义一个人的状态
Function:
考虑两个人的状态做状态更新
Initialize:
Answer:
先思考最小状态
然后思考大的状态-> 往小的递推，那么非常适合记忆化搜索
记忆化搜索
本质上：动态规划
动态规划就是解决了重复计算的搜索
大部分DP都可以用记忆化搜索做
动态规划的实现方式：
循环（从小到大递推）
记忆化搜索(从大到小搜索)
画搜索树
万金油
什么时候用记忆化搜索？
状态转移特别麻烦，不是顺序性。
初始化状态不是很容易找到
题目类型
博弈类问题
区间类问题
适合解决题目
状态特别复杂
初始化不好初始化。