概念
动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
DP问题是Leetcode中的经典问题,也是面试中经常考到的类别之一,没有通用的模版,有些DP题思考的过程也比较繁琐.所以这篇总结可能会不断更新,以便达到更好的效果
适用场景
- 找Max, Min的问题
- 发现可能性的问题
- 输出所有解的个数问题
不适用场景
- 列出所有具体方案(起码是指数级别的复杂度,通常是递归,backtracking)
- 集合问题
考虑
Warm Up
爬梯子
作为DP的入门题来说,思考过程还是很重要的。 一次可以爬1级或者两级的台阶,问有多少种爬法。
符合输出所有解个数的问题。
因为只能爬一级或者两级所以到N级的话,你只能从n-1爬到n或者n-2爬到n;这样说来,如果dp[n]
代表到n级台阶有多少种可能性的话,转移方程为dp[n] = dp[n-1]+dp[n-2]
所以代码很容易写出
1 | def climb(n): |
当然这道题有优化条件,否则就没有必要花大篇幅写了。通过分析状态转移方程可以发现dp[i]
只与dp[i-1],dp[i-2]
有关,说明再之前的状态是不会影响到当前状态的,所以我们可以通过只保留两个状态来不断滚动从而求出最后的结果。
1 | public class Solution { |
进而我们能看出,如果当前状态只与前面的相关的话,我们都可以通过滚动数组,变量来简化空间复杂度–这种尤其适合不太复杂的动态规划问题,简单的二维DP
53. Maximum Subarray
找Max问题
很容易得出当前局部最大+当前值,和当前值的对比,而从决定是继续加还是从新来过
1 | class Solution(object): |
从上一段分析可以看出,dp状态只与上一个状态有关,从而可以简化成变量来储存dp[]
1 | class Solution(object): |
300. Longest Increasing Subsequence
找出Max
这道题有点不一样的地方是最后的结果有可能是任意一个位置,所以不是简单的return dp[-1]
而是max(dp)
dp[i] = 1 + max(dp[j]) j < i and A[i] > A[j]
1 | class Solution(object): |
139.Word Break
寻求解的存在性
和上一题有点像,dp[i] 为当前字符满足之前的字符在字典里
1 | class Solution(object): |
198. House Robber
dp[i] = max(dp[i-2]+A[i], dp[i-1])
当然一共就3个状态,我们也可以通过类似爬梯子的方式,把空间复杂度降为O(1)
1 | class Solution(object): |
303. Range Sum Query - Immutable
简单的累加求和做为DP,则转移方程为res(x,y) = dp[y] - dp[x-1]
1 | class NumArray(object): |
Medium
368. Largest Divisible Subset
这道题需要一点思考,除了创建一个DP数组来记录到i位置最长的长度之外,我们还要知道其对应能整除的数字,所以还需要一个array来记录上一个数字的位置。dp的默认值为1, pre的初始值为None就是没有对应的数字;当且仅当dp需要更新的时候,更新其上一个能整除数字的index。最后找出max(dp)所对应的数字,根据其pre的index逐个找数字,输出。
1 | class Solution(object): |
338. Counting Bits
需要熟悉Bit运算和概念,要能发现countbit(n) = countbit(n/2) + n % 2这么一个方程,就是说一个数乘2意味着bit位左移一位
1 | class Solution(object): |
264. Ugly Number II
用三个dp存2,3,5出现作为乘子的个数
1 | class Solution(object): |
673. Number of Longest Increasing Subsequence
相关题目,需要额外数组来记录已经出现最长的次数,也就是说如果前面有多个长度相等的连续子串的话,cnt要一直+1
1 | class Solution(object): |
309. Best Time to Buy and Sell Stock with Cooldown
这道题一开始确实想不出来,感觉情况太多了;我承认有些DP题就是想不出来怎么做…..后来看到Discuss上有一个解法很不错,就是我们就考虑buy和sell的情况,buy的情况是最大利益只和前一个状态有关或者前两个状态的时候卖,然后这时候买。所以DP的定义就是buy[i] 在i的时候和在i之前买的最大值buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
同理,sell的时候也和之前状态有关sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
1 | class Solution(object): |
矩阵DP
这种问题需要初始化DP数组,第0行和第0列,这样会方便之后的操作,通常这种问题是只能向右或者向下操作,否则则需要用BFS–求最短路径;DFS来解决
Warm Up
62. Unique Paths
符合求解的个数问题dp[i][j] = dp[i-1][j] + dp[i][j-1]
1 | class Solution(object): |
当然我们知道每一个dp状态只与上方或者左方的状态相关,所以可以考虑通过某种方式来保存状态;一种方法是建立一个额外数组来存储列状态,dp变成一维存行状态;不过更进一步的话,每一个dp[i]状态就意味着当前从i行过来的状态总数,这里还是贴图吧,更好理解
1 | class Solution(object): |
63.Unique Paths II
初始化首行首列的时候如果有障碍的话,就都变成0了
1 | class Solution(object): |
64. Minimum Path Sum
1 | class Solution(object): |
题目变成了正方形,逐层扩展的时候要记录,每一列计算之前要加上第0行第j列的值,所以沿用上一题的图,dp[i] = dp[i]–上方的值+ dp[i-1] – 左方的值
1 | class Solution(object): |
256. Paint House
由于每次喷涂的房子颜色不能与之前的相同,所以转移方程为dp[i][2] += min(dp[i-1][0], dp[i-1][1])
dp为costs
1 | class Solution(object): |
276. Paint Fence
这道题其实跟上一道题很像,但是每一次涂得颜色可以和上一个一样(连续的颜色最多出现两次),所以当前状态与前两个有关,可以和前两个状态其中任何一个颜色一样 dp[2] = (k-1) * (dp[0] + dp[1]), dp = [k, k*k, 0]
1 | class Solution(object): |
174. Dungeon Game
最主要的区别是,要从后往前找,由于生命最少为1,所以DP的条件也要相应变一下
1 | class Solution(object): |
Medium
651. 4 Keys Keyboard
这道题想了半天,发现最后还是举例子最好;在6个操作内,只有A的操作是最大的,之后的话dp[i] = dp[j] (i-j-1), 比如i==7, j==1的时候,最后是A 7-1-1 = 5A
1 | class Solution(object): |
304. Range Sum Query 2D - Immutable
这道题最关键的是处理corner case
1 | class NumMatrix(object): |
221. Maximal Square
可行的解法是很巧妙的:以这个square的最右下角的位置作为存储点f(i, j),当matrix(i, j)是1的时候,f(i, j) = min{f(i - 1, j - 1), f(i - 1, j), f(i, j -1)} + 1. 这是因为如果这是一个square,那么构成这个square的最基本条件就是跟它相邻的边的最小所在square.所以一个square的f值如下:
1 | class Solution(object): |
二维DP
72. Edit Distance
这道题是一道经典问题,分为之下三个操作,我觉得以下的解释是最好的
a) 插入一个字符:word1[0:i] -> word2[0:j-1],然后在word1[0:i]后插入word2[j]
DP[i+1][j+1] = DP[i+1][j]+1
b) 删除一个字符:word1[0:i-1] -> word2[0:j],然后删除word1[i]
DP[i+1][j+1] = DP[i][j+1]+1
c) 替换一个字符:word1[0:i-1] -> word2[0:j-1]
word1[i] != word2[j]时,word1[i] -> word2[j]:DP[i+1][j+1] = DP[i][j] + 1
word1[i] == word2[j]时:DP[i+1][j+1] = DP[i][j]
1 | class Solution(object): |