leetcode习题分类汇总- Dynamic Programming篇

Unique Binary Search Trees-给定n返回所有可能的二叉搜索树的数量

思路:主要是问题规约,
对于BST是否Unique,很难判断。最后引入了一个条件以后,立即就清晰了,即
当数组为 1,2,3,4,.. i,.. n时,基于以下原则的BST建树具有唯一性:
以i为根节点的树,其左子树由[0, i-1]构成, 其右子树由[i+1, n]构成。
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目,

如果数组为空,毫无疑问,只有一种BST,即空树,
Count[0] =1

如果数组仅有一个元素{1},只有一种BST,单个节点
Count[1] = 1



如果数组有两个元素{1,2}, 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] Count[1] (1为根的情况)
+ Count[1]
Count[0] (2为根的情况。

再看一遍三个元素的数组,可以发现BST的取值方式如下:
Count[3] = Count[0]Count[2] (1为根的情况)
+ Count[1]
Count[1] (2为根的情况)
+ Count[2]Count[0] (3为根的情况)

所以,由此观察,可以得出Count的递推公式为
Count[i] = ∑ Count[0…k]
[ k+1….i] 0<=k<i-1
问题至此划归为一维动态规划。


动态规划,感觉最重要的是递推式和初始值



### Unique Binary Search Trees II-同上,这次直接返回树了

思路:


这道题是求解所有可行的二叉查找树,从Unique Binary Search Trees中我们已经知道,可行的二叉查找树的数量是相应的卡特兰数,不是一个多项式时间的数量级,所以我们要求解所有的树,
自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解,也就是N
-Queens
中介绍的在循环中调用递归函数求解子问题。
思路是每次一次选取一个结点为根,然后递归求解左右子树的所有结果,
最后根据左右子树的返回的所有子树,依次选取然后接上(每个左边的子树跟所有右边的子树匹配,
而每个右边的子树也要跟所有的左边子树匹配,总共有左右子树数量的乘积种情况),
构造好之后作为当前树的结果返回。
实现中还是有一些细节的,因为构造树时两边要遍历所有左右的匹配,然后接到根上面。
当然我们也可以像在Unique Binary Search Trees中那样存储所有的子树历史信息,然后进行拼合,虽然可以省一些时间,
但是最终还是逃不过每个结果要一次运算,时间复杂度还是非多项式的,并且要耗费大量的空间,
感觉这样的意义就不是很大了。





Maximum Subarray-寻找和最大的连续子数组

思路:一维DP,维护一个最大值,遍历,不断计算包含i的前i个元素的最大值,避免前i-1最大值的重复计算,时间n,空间n



Maximum Product Subarray-求最大乘积的子数组

思路:(1)记录每种情况的最大值,O(N2)

(2)一维DP,注意和加法的不同,可能出现负数,所以在维护最大值的同时也要维护最小值,O(N).



Best Time to Buy and Sell Stock-一天中T+1买卖股票获得的最大利润

思路:一维DP,维护一个maxProfit和一个前i时间段内的最小值,可以复用前i-1时间段内最小值的重复计算,时间n;



Best Time to Buy and Sell Stock II-一天内T+0买卖股票获得的最大利润

思路:贪心,逆向遍历,就是只要有利润那就买卖,最终求出最大值,额,有技术含量吗…时间N



Minimum Path Sum-矩阵的最短路径问题

思路:经典二维DP,维护到当前步骤的最小值,复用,直到最后一个最小值出现。时间N.



Jump Game-测试数组是否可以从前跳跃到尾部

思路:贪心?..遍历,记录出每次跳跃的最大步骤max,其实只要知道什么时候false的条件就可以了,max<=i而且当前A[i]=0的时候,大概这种题主要就是考验细心吧,至于DP,在求max的时候要用到,贪心是DP的特殊情况,没看出来,容我日后补补。时间N



.Jump Game Two- 测试数组从前跳跃到后面的最小步数

思路:
比较典型的贪心。维护一个区间,区间表示第i步所能到达的索引范围。递推的方法为:
每次都遍历一遍当前区间内的所有元素,从一个元素出发的最远可达距离是index+array[index],那么下一个区间的左端点就是当前区间的右端点+1,下一个区间的右端点就是当前区间的max
(index+array[index]),以此类推,直到区间包含了终点,统计当前步数即可。



### Unique Paths-mn个方格机器人从左上到右下一共多少种方案

思路:二维DP,构造二维数组,用数字表示走到当前格子有多少种方法,递推式就是当前格子等于左边加上上面格子的总方法,不断复用,遍历矩阵得到结果,时间n,空间n.








Unique Paths II-同上,假设有障碍物有多少种方案

思路:递推式还是跟UniquePaths一样,只是每次我们要判断一下是不是障碍,如果是,则res[i][j]=0,否则还是res[i][j]=res[i-1][j]+res[i][j-1]。还是没习惯一维数组的解法,感觉二维的更加直观。




### Climbing Stairs-N级阶梯每次1-2步,多少种方案到达终点

思路:把握初始值,利用当前方案数等于n-1和n-2的方案之和,一维DP




### House Robber-偷窃,相邻的房子不能偷,求获利最大值

思路:
极值的问题首先考虑动态规划Dynamic Programming来解,
依然是初始值,递推式,维护当前房子的最大值,

状态转移公式为: dp[i]=Math.max(dp[i-3]+num[i], dp[i-2]+num[i])。


*HouseRobberTwo -同上,不过房子连成一个环

思路:

讨论是否抢劫第一件房屋。如果是,则不可以抢最后一件房屋。否则,可以抢最后一间房屋。

以此为依据,将环形DP问题转化为两趟线性DP问题,可以复用House Robber的代码。

另外需要特判一下只有一件房屋的情形



Edit Distance-计算从一个单词转换到另一个单词的最小操作数,可以进行替换,插入,删除操作

思路:二维DP:
两个String看成两个char数组,分别是x[m]以及y[n]。对于x[1]…x[i]和y[1]…y[j]的edit distance为A[i][j]。那么有如下recursion:

A[i][j]=A[i-1][j-1] if x[i] = y[j];

A[i][j]=min(A[i-1][j], A[i][j-1], A[i-1][j-1])+1 if x[i] != y[j]

其中第二种x[i]!=y[j]的min中的三个元素分别代表insert, delete和replace三种情况,要看哪种最小。

Base case是A[0][j]=j, A[i][0] = i。

依然是记录当前位置的最小操作数,局部最优解,重复子问题,状态转移方程式。思路相同,不过是不同问题的抽象化。


Distinct Subsequences-

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
思路:When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. The key
is to find the changing condition.

遇到这种两个串的问题,很容易想到DP。但是这道题的递推关系不明显。可以先尝试做一个二维的表int[][] dp,用来记录匹配子序列的个数(以S =”rabbbit”,T = “rabbit”为例):
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
从这个表可以看出,无论T的字符与S的字符是否匹配,dp[i][j] = dp[i][j - 1].就是说,假设S已经匹配了j - 1个字符,得到匹配个数为dp[i][j - 1].现在无论S[j]是不是和T[i]匹配,匹配的个数至少是dp[i][j -
1]。除此之外,当S[j]和T[i]相等时,我们可以让S[j]和T[i]匹配,然后让S[j - 1]和T[i - 1]去匹配。所以递推关系为:
dp[0][0] = 1; // T和S都是空串.
dp[0][1 … S.length() - 1] = 1; // T是空串,S只有一种子序列匹配。
dp[1 … T.length() - 1][0] = 0; // S是空串,T不是空串,S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()

……

总结:DP有些类似数学归纳法,最重要的是观察,局部最优解,重复子问题,找到状态转移方程式是关键,经常在求极值(不断维护当前极值),字符串序列和匹配(当然也可以用regex)等问题遇到,这部分,自己掌握的一般,难度也比较大,因为问题比较抽象,所以有时即使知道是DP也不一定可以解决出来。