Lecture 1 Introduction
什么是动态规划？
- 1.计数型
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是Sum
- 2.求最大最小值
- 从左上角到右下角的路径的最大数字和
- 最长上升子序列长度
- 3.求存在性
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和是sum
- Coin Change(最大最小型)
- 一般想法：先用面值大的硬币，最后想办法用小硬币
- 动态规划四个步骤
-
- 确定状态
- 一般来说，解决动态规划需要开一个数组，可能是一维的或者二维的，要确定数组的每一个元素代表什么
- 转移方程有几个变量就需要创建几维数组
- 确定状态需要两个意识：最后一步是什么，子问题是什么
-
- 转移方程
- 每个子问题到下一个子问题的过程
-
- 初始条件和边界情况
- 什么时候停下来？初始条件是什么?
-
- 计算顺序
- 一般是从小到大
- Coin Change
- 从第一步算到m步，每一步算n次，其中m为最后的硬币sum，n为总共有多少种不用的硬币，时间复杂度为O（m*n）
- 最后一步是由前面几步的最小值确定的，所以先确定前面的值，从小到大，就能判断出最后一步的值
- Unique Path:计数型
- Jump Game：存在型
Lecture 2 Coordinates and Bit Operation
- 序列型：前i个，最小，方式数，可行性。。
- Paint House
- 分别记录每栋房子之前的房子的每种颜色的最小花费
- 划分型
- Decode ways
- 解密数字串即划分成若干段数字，每段数字对应一个字母
- 知道前N-1和N-2个数字分别有多少种方式，再相加
- 坐标型
- 需要找到序列中某些子序列或者网格中的某条路径：计数，最大，最小，存在性
- Minimum Path Sum
- 空间优化：计算第i行时，只需要i行和i-1行的f值（滚动数组）
- Bomb Enemy
- 给定输入为序列或者网格矩阵
- 问题一般为：以第i个元素结尾的某种性质，到格子（i， j）的路径的性质
- Minimum path sum打印路径：新建一个二维数组，记录每次的方向，然后从最后（右下角）往前推，最后记住要反转数组才是从开始到结束的顺序
- 位操作型动态规划
- Counting bits: removing the last bits
Lecture 3 Sequence
- 给定一个序列，转移方程f（i）下标i表示前i个元素的某种性质， f(0)就是空序列的性质
- Paint House II: Similar to Paint House I, Optimization: pick the smallest and the second smallest cost of all colors, reduce the min calculation to O(1) and totoal time complexity from O(N * K * K) to O(N * K * 2), where N is the number of houses and K is the number of colors
- House Robber
- House Robber II:想办法把圈断开，分两种情况处理，变成两种序列情况
- Buy and Sell Stock III:分成五个状态，分别记录下每天每个状态的情况（类似于Paint house）
- Russian Doll Envelope
Lecture 4 划分型，博弈型，背包型
- 划分型
- Perfect Squares
- Palindrome Partitioning II:1. find all possible palindrome from the string s ans store them in a 2d array expand palindrome start and end index to both sides. 2. partition dp: dp[i] = min(dp[i], dp[j] && isPalin(s[j][i - 1]))
- Copy Books(LintCode)
- 划分型dp关键字：连续！Substring, continuous subarray
- 博弈型(两方游戏)
- 从第一部开始分析!!!问题规模会越来越小。
- Coins in a line: Alince and Bob takes one or two coins each turn
- Alice先手还剩N个Coin，与Bob先手还剩N-1个Coin是一样的，所以每个局面都可以看成是先手但是剩下不同数量的Coin
- 背包型
- 你有一个背包，背包有最大承重
- 商店里有若干物品，都是免费拿
- 目标： 1. 装下最多重量的物品， 2. 装下最大总价值的物品。 3. 有多少种方式正好带走满满一书包物品
- 给定背包最大承重M， 物品的重量都是整数
- 每个方案的总重量都是从0到M
- 对于每个重量方案，我们要知道能不能做到
- Note：背包问题中，dp数组大小和总承重有关
- 现在需要知道前N个物品能否拼出重量W
- 如果前N-1个物品能拼出W，当然前N个物品也可以拼出W
- 如果前N-1个物品能拼出W-A(N-1),A(N-1)为第N个物品的重量，那么前N个物品也能拼出W
- BackPack I - V
- Coin Change 1, 2
- 当每个物品只能用一次时，需要多开一维的dp数组去计算前N个物品的方式
Lecture 5 背包型, 区间型
- 背包型
- Backpack II：现在每个物品有价值，求能带走最大多少价值的物品
- f[i][j]: 用前i个物品拼出重量j时的最大总价值，j = -1表示不能拼出
- dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + Value[i - 1])
- 区间型：当子问题还是连续的index时
- Scramble String
- Burst Ballons
- 消去型的题目要从后往前想，最后一步只剩一个，然后往前想
- 先从小的len开始计算
Lecture 6 双序列型
- 有两个序列
- 每个序列本身是一维的
- 可以转化为二维的动态规划
- 查看最后一个字符是否匹配，缩减问题规模
- 易错点： 记得初始化，空串处理，结果是否 + 1
- Longest common subsequence
- Interleaving String
- Edit Distance
- Distinct Distance
- Regular Expression Matching
- Wildcard Matching
- Ones and Zeros
