继续讲动态规划，这节课讲了三种类型的动态规划：
- 区间类：
- 求一段区间的解max/min/count
- 转移方程通过区间更新
- 从大到小的更新
- 匹配类：
- 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] min/max/数目/存在关系
- n = s1.length()，m = s2.length()
- 背包类
- 用值作为DP维度
- Dp过程就是填写矩阵
- 可以滚动数组优化
区间类经典的三道题：
• coin in a line III
• stone game
• scramble string
匹配类的题目：
• Distinct Subsequence
• Interleaving String
• Minimum Adjustment Cost
背包类的问题：
backpack I, II, III, IV，ksum
网友评论