九章 - 动态规划笔记
什么情况下使用动态规划
满足下面三个条件之一，则极有可能使用动态规划 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都可以用记忆化搜索做
动态规划的实现方式：
- 循环（从小到大递推）
- 记忆化搜索(从大到小搜索)
- 画搜索树
- 万金油
什么时候用记忆化搜索？
- 状态转移特别麻烦，不是顺序性。
- 初始化状态不是很容易找到
题目类型
- 博弈类问题
- 区间类问题
- 适合解决题目
- 状态特别复杂
- 初始化不好初始化。