Leetcode按题目类型总结(十三)

动态规划

Posted by Jingming on December 30, 2017

所有代码详见:https://github.com/jingminglake/Leetcode

总体思路

动态规划适合求解的问题类型是最值类型,也就是求解决方案中最优的,例如最大值,最小值,最好方案情况,方案个数。

  • 求方案个数 求解有多少个解的问题,一般是使用分治法,也就是递归的解决问题,可以使用动态规划去优化解题思路:使用记忆化搜索,或者是直接构造解题顺序,基于已经解决的子问题来一步步推导。

  • 求最值 例如,求最大子数组大小。突破思维局限,可以宏观看问题,分为以最后一个值为结尾的情况和不以最后一个值为结尾的情况,然后,从大小为1的数组开始往后推算,得出答案。

例如,最长回文串大小。可以采用二维子问题的方法,也就是将问题变成二维的公式,然后根据公式确定二维的双重循环计算顺序(方法是看公式中是如何依赖前面信息)。

  • 动态规划编程模板

一种是递归型加hashmap的记忆化搜索;一种是是构造型,构造型的以0为结尾,然后构造以1为结尾,每次x依赖于前面以0到x-1为结尾中的最优解。

  • 常见题型以及应对
  1. 多个元素相加等于target的组合数

(1)元素是独特(distinct)的,且元素可以重复选,且[1,2]和[2,1]都算答案。

解:这种题目的模型就是爬楼梯,爬楼梯的走法就是答案,每次都多少步是有限制的,但是可以重复。

解就是看到target的最后一步有几种走法。

(2)元素是独特(distinct)的,且元素可以重复选,但[1,2]和[2,1]算重复情况,只能选一种。

解:这种题目的模型就是完全背包(物品可以重复选,价值为1)。也就是说,在1+2等于2+1的情况下,总的来说都是价值为3的东西,所以算重复情况。

完全背包的解法是新加入一个维度:可选数字的集合(以0开始并以i下标为结束的集合),相当于每次比之前多考虑一个新加入的元素。

这样每一步当前物品的选择都是基于之前的元素的所有选择情况决定的,也就是说,先考虑1,再考虑2,就避免了出现[1,2]和[2,1]这种重复的情况。

物品可以重复选的时候,递推公式里面,target除了依赖上一层集合不选当前i元素直接过来的,而且要依赖同一层之前计算的多个结果(也就是基于该值反复选第i个元素累加得到target)。

(3)元素不一定独特的,但是元素只能选一次,[1,2]和[2,1]算重复。

解:这种题目模型是01背包(价值为1)。由于[1,2]和[2,1]算重复,01背包仍然需要第二维的信息。递推公式里面,target除了依赖上一层集合不选当前i元素直接过来的,或者选择当前的i,也就是减去i的之前计算的结果。

总结:如果组合顺序先后有区别算重复,那么是二维背包。

PS. 要考虑当前加入的元素对之前所有状态的贡献,其中状态甚至可以是子最优解。

具体题目

5. Longest Palindromic Substring

题意:求字符串中最长的回文串。

:方法一:动态规划。dp[i][j]表示下标i到下标j的字符串是否回文,最先看i和j是否相等,如果相等,则是回文串(因为是一个字符)。然后看i和j之间的差值是不是1,如果是,说明此时是两个字符的串,也就是看s[i],s[j]是否相等,相等则是回文串。最后看i和j之间的差距是2以上的,要看s[i],s[j]是否相等,以及i+1到j-1之间是否回文,也就是说dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]。 计算顺序是:作图可知,每个格子依赖自己左下方的格子,且一开始初始知道的值是对角线,因此,可以从左到右从上到下一列列的来计算,也可以自下向上,从左到右一行行的计算。扫描时候,顺便记录最长子串且回文的起始下标和长度,最后截取出来作为答案即可。

方法二:每个字符作为中心进行扩展,看能组成的最长回文串,保存一个全局变量最大长度即可。扩展的时候,分为奇数扩展和偶数扩展两种情况。第一种是把当前字母作为中心,第二种,把当前字母和下一个字母作为中心。

PS. 此题动态规划思路的模型就是,把母串拆成n^2个子串,然后从两边扩充这些子串达到较大的子串,最终得出答案。

此题中心扩展的思路就是,子串中以某个元素作为基点扩充,最终答案必然存在于其中一种情况中。

516. Longest Palindromic Subsequence

题意:此题和第5题不同之处在于,subsequence不是substring,而是可以不连续的字符组成的子串。

:动态规划。dp[i][j]表示下标i到下标j区间内最长的回文串。那么对于求dp[i][j]来说,两种情况,一种是s[i] == s[j],那么dp[i][j] = dp[i-1][j-1] + 2; 另一种是s[i] != s[j],那么意味着dp[i][j] = max{dp[i+1][j], dp[i][j-1]}。

实现细节,由于i,j与i+1和j-1有关,画图可知,依赖的是左边格子、下边格子以及左下边的格子。也就是可以从左向右,从下向上一列列的计算,也可以是从下向上,从左到右一行行的计算。

优化:可以使用一维数组做dp数组来替代二维dp数组。只需要一个一维的滚动数组。此题比较特殊,因为依赖的三个格子,一维数组如果保持和二维一样的逻辑是行不通的,因为访问顺序存在冲突,但是此题仍然可以使用一些技巧来达到只使用一维数组,因为dp[j]总是增大的,因此只需要记录每一行最大的就可以了,只要出现s[i] == s[j](i != j),可以肯定的就是dp[j]等于上一行的最大值加2。

PS.此题虽然是子序列相关问题,但是仍然可以拆为n^2个子串,然后还是对子串两侧的扩充。

139. Word Break

题意:能否把串切分成单词。

:动态规划,dp[i]表示0到i串是不是可以切割,难的地方在于,要设置一个起点,也就是空串dp[0] = true来保证一个单词是一个子串的时候,也为true。只要其中一条路能走通,那么当前下标对应的子数组结果就为true。

如果不使用dummy起点,那么一定要先判断是不是一个单词的情况。

PS.此题可以是topdown的,但是显得比较乱,且为了标记子串,需要消耗大量空间。更好的方法就是bottomup,也就是想计算0-n-1的串,可以先计算0-1, 0-2,0-3,…这些子串是true还是false,这样标记真假只需要一个int型的下标表示以i结尾就可以了。

517. Super Washing Machines

题意:给你一个数组,每个元素表示一台洗衣机洗的衣服数量。然后现在每台机器可以一回合移动一件衣服到相邻的机器。问需要几个回合后,可以让所有机器洗衣数量相等,也就是所有数组的值相等。如果做不到,那么返回-1。

:首先,可以把衣服数量当做波峰波谷来看,一个波峰如果从一个方向(例如向右)出发,平均每回合可以把自己的1传到右边任何一个点。例如[3,0,0,1]。3传给旁边的0,虽然旁边的0一开始是不能传的,但是0变1后就可以继续传给右边了,所以说,例如3比最终平均值大2,在向右传递两次的情况下,平均上每次都可以把1个盈余的部分放入任何右侧亏欠1的部分。

使用L来记录某个元素为基准点的左边(不包括当前元素)所有机器缺少的衣服数量,R来记录当前访问元素的右边(不包括当前元素)所有机器缺少的衣服数量。如果L和R都大于0,说明当前元素是波峰,当前元素向两侧输送元素的过程中,一次只能向一个方向输送一个,因此如果以当前元素作为考虑点来进行负载平衡,那么次数将是L+R。

如果L和R一正一负,那么说明自己是波峰或者波谷。例如abs(L) < abs(R),L < 0,R > 0,那么说明自己是波峰,如果要平衡,那么是左边加上自己的盈余部分移到右边作为结果。但是换个角度来看,左边加上自己,其实就是等于右边abs(R)。

总之,一正一负这种情况,结果是max(abs(L), abs(R))。

如果L和R都小于0,说明当前元素是波谷。那么两边元素可以同时向自己进行运输,所以此时结果取决于慢的那一侧,也就是max(abs(L), abs(R))。

然后,我们对每个元素作为基准点,考虑一遍运输,然后从中选出最少的次数作为结果即可。

使用动态规划中的累加数组来减少左右和重复计算。

53. Maximum Subarray

题意:求包含正负整数的arry最大subarray的大小。

:方法一:先计算出前缀和数组,发现其中pair中相减(下标大的减下标小的,或者说右边的减去左边的)最大的那个就是答案。看似需要n^2时间,但是可以使用一个变量记录左侧遇到的最小值,然后把当前扫描的值都和之前的最小值减一下,得出一个答案候选值,这样只需要n时间。

该方法前缀和数组消耗O(n)空间。可以使用滚动数组来减少空间为O(1)。

方法二:动态规划,模型就是分治法把问题化简为子问题,然后记录子问题中间值从而减少重复计算来达到优化。问题f(n)分解为两个问题:一个是该最小数组一定包含最后一个数,另一个是该最小数组一定不包含最后一个数。 可以知道,问题的解就在于两个问题中。第二个问题中,我们很容易知道f(n) = f(n - 1);对于第一个问题,我们先将它的解记为g(n),那么我们有 g(n) = max {g(n - 1) + A[n], A[n]},理解:子数组是要求连续的,所以问题分解为:一,要么只选最后一个;二,要么倒数第二个也得选,也就是g(n - 1)问题加上最后一个元素A[n]。

总之,公式就是: f(n) = max {f(n - 1), g(n)}, max {g(n - 1) + A[n], A[n]},也就是说f(n)的解是 f(n - 1),g(n - 1) + A[n], A[n]三者中的最大的那个。要求f(n),那么从计算f(0)开始,计算f(1), f(2), … f(n),每一步都用到之前计算结果。

上面的公式在编程时候可以空间简化为全局最优和局部最优只需要分别保持一个变量就可以了,由于他们都是只依赖前一个值。

使用动态规划方法的缺点是不知道这个最大子数组的起始和结束下标。

91. Decode Ways

题意:A到Z分别使用1到26表示。现在给出一个数字串,求可以所有可能的字母组合数量。

:此题不需要求解具体的组合,可以使用动态规划可以求解。

dp[n]表示以index n为下标为结尾的串的组合数。该问题拆解为两种问题,一种是最后一个数字作为一个字母的情况,另一种是最后两个数字作为一个字母的情况。

有公式:dp[i] = combination(s[i]) * dp[i - 1] + combination(s[i-1], s[i])*dp[i - 1]。

考虑数字串的最后一位的组合。如果最后一位不为0,那么combination(s[i]) == 1,否则combination(s[i]) == 0。再看最后两位(一定要两位一起看!)对应的数字,如果是[10, 26],那么combination(s[i-1], s[i]) == 1,否则combination(s[i-1], s[i]) == 0。

PS.此题中。“01”的decode方式是不合法的,也就是说不能将01当作1。不能只考虑最后两位的组合,而是要先考虑最后一位的组合,再考虑最后两位的组合。另外,边界条件要注意:看输入字符串是否为空,或者长度小于2。

另外,此题状态只与前两个数有关,可以使用滚动数组将空间复杂度优化到O(1)。

639. Decode Ways II

题意:此题与91不同之处在于,可以使用’*‘表示1到9中任意一个数。

:dp[i] = combination(s[i]) * dp[i - 1] + combination(s[i-1], s[i])*dp[i - 1]。解题公式与91完全一样,不同之处在于组合数变得更加多样。可以单独设计一个计算组合数的函数。

现在来分析组合情况,考虑一个数作为一个数字的情况,也就是combination(s[i])的情况:当s[i] == ‘0’,那么combination(s[i])==0;当s[i] == ‘*‘,那么combination(s[i])==9;当s[i] 属于1到9,那么combination(s[i])==1。

考虑两个数作为一个数的情况:如果是’**‘,那么combination(s[i-1], s[i])==15,因为第一个*作为0考虑的时候,其实是非法的,也就是说两位数情况不存在0到9。

如果是’*digit’,那么digit属于0到6的时候,combination(s[i-1], s[i])== 2,否则,combination(s[i-1], s[i])== 1。理解就是digit属于0到6的时候,存在1+digit和2+digit两种情况。

如果是’digit*‘,那么digit为‘1’的时候,combination(s[i-1], s[i])== 9,如果digit为‘2’的时候,combination(s[i-1], s[i])== 6,否则combination(s[i-1], s[i])== 0。

其余的情况就是只有数字的情况,与91题一样。

PS.可以使用滚动数组优化空间从O(n)到O(1)。另外,此题结果的数可能很大,因此题目要求返回结果mod 1000000007。

650. 2 Keys Keyboard

题意:一开始只有一个A,只有拷贝粘贴两种操作,求到达n个A所要经过的步数。

:此题使用动态规划,n可以从之前任意一个数过来。 例如12,那么经过3的拷贝加粘贴3次,也可以是4拷贝1次粘贴2次,也可以是6复制1次粘贴1次,也可以是1通过复制1次粘贴11次达到。其中到达3,4,6需要多少步是一个子问题,之前计算过了,所以要从中间选择最小的。 公式就是dp[i] = min (dp[j] + i/j), 1 <= j <= i / 2 && i % j == 0。 还有优化方法就是:j满足i % j == 0,且越大,一定不小于j比较小的,所以j从大到小遇到第一个i % j == 0的就直接返回。

PS.此题是典型的整数n从之前任意一步较小的过来的动态规划模型。

651. 4 Keys Keyboard

题意:一开始是空,有四种操作:打一个字符A、全选、复制、粘贴。给出操作步数N,求能打出的最多的A数。

:动态规划。例如N=7,只是把3个A粘贴了两遍。长远来看,操作步数为k时候打印最多的A的模式就是:AA… + 全选、复制、粘贴、粘贴…。这种模式中只可以全选复制一次,因为之前的AA..里面可能包含更多的全选复制,但是我们只考虑最后一步到达的模式,也就是只全选复制一次,粘贴多次的情况。

所以操作步数为k时候的最优解取决于前面i步生成的A,加上最后面k-2-i步粘贴次数的选择。理解:前面的A由操作步数为i来最大化生成。结果就是第i步的结果增大了(k - 2 - i) 倍,i的选择范围是[1,k-3]。另外就是:dp[k]至少是k,因为可以通过全进行输入A操作得到。

建立动态规划数组dp,dp[i]表示只有i步的最大结果,那么方程可以列为:

dp[k] = max {k, max { dp[i]*(k - i - 1)} }, 1 <= i <= k-3。其中也可能出现没有全选、复制、粘贴,而全部是直接打印A得出最大结果的情况。

198. House Robber

题意:数组里面下标代表房子index,值大小代表能偷的价值(大于等于0),相邻房子不能偷,求最大能偷多少。

:方法一:动态规划,dp[i]表示第i个房子为结束的最大值,也就是子问题,最终答案是dp[n-1]。

由于价值不小于0,所以dp[i]其实是保持递增的,那么不需要考虑i-2之前的dp,公式是dp[i] = max {dp[i-2] + nums[i], dp[i-1]},前者是一定选i,后者是一定不选i。这样,时间复杂度降为O(n)。接下来,还可以使用滚动数组来优化空间为O(1)。

PS. (1)如果存在负数,那么此题动态规划的思路与求连续最小子数组的和的模型是一样的,即局部最优和全局最优,有负数的情况下,对于i下标的问题,他的局部最优是一定选自己的,所以是倒数第三步的全局值加上自己,或者是自己本身,全局值就是倒数第二步的全局和当前局部谁较大。

(2)为什么不能只选奇数总和和偶数总和:看测试用例 [2,1,1,2],选择开头和结尾的2,总和4是最优解。

(3)为什么不能强制以i为结尾。因为这样考虑的话,每个以i强制结尾的公式并不是dp[i] = dp[i-2] + nums[i],而是dp[i] = max {dp[i-2] + nums[i], dp[i-3] + nums[i]}。

最终的答案,是看所有dp[i]里面最大的。这个公式不适合有负数的情况。

213. House Robber II

题意:在198题的基础上,房子现在围成一圈。

:此题在198题基础上,计算两次,一次是去掉第一个房子,表示不去第一个房子,第二次是去掉最后一个房子,表示不去最后一个。结果是两者之中较大的。原理是:(1)答案必会在两种情况中产生。(2)每种情况中,都无需考虑两头的房子会冲突的问题,问题简化为198题。

337. House Robber III

题意:输入是二叉树,值都大于等于0,相邻结点不能都选,最终能偷最大为多少。

:使用分治法,每个结点计算两个值,一个值表示选择当前结点最优解,另一个值表示不选择当前结点可以得出的最优解。这样,每个结点选自己的解,一定要从左右子树中的不能选择自己的最优解加起来;如果每个结点不选自己的话,那么他左右孩子结点是可以选自己,也可以不选自己,所以要取较大者,这点比较难想到,

理解:例如不选左孩子,那么能选左孩子的孩子,也许会更大。

PS. 如果存在负数,那还是使用局部最优和全局最优解法。

174. Dungeon Game

题意:MxN矩阵要从左上角的格子走到右下角的格子(只能向右走或向下走),遇到正数加血,否则减血,血量不能小于等于0。现在求英雄最少初始血数就可以到的右下角格子救公主。 英雄在第一个格子也会掉血或者加血。

:首先想到此题是递归的,也就是当前格子递归到求右边和下边的格子的初始血量,如果右边和下边的格子初始血量要求是x,那么进入该格子的时候,血量一定要大于等于x,也就是说,在两者中选择较大的作为结果。当然会出现大量的相同结点,所以此题是动态规划,dp数组表示从当前点出发的最少初始血量。

使用自底向上的方法,那么要从终点处(右下角的格子)出发。每个格子只依赖计算右边和下边的格子,但是发现最右下角的格子的上面的格子不存在右边格子,同理,最右下角格子左边格子不存在下面的格子。所以首先在矩阵下方和右边分别加入一个行(列)dummy node。

自下而上,从右至左进行扫描。需要具有的最少血是右方、下方中最小值加上当前格子的消耗。消耗为负,就转为正加上去。注意的是,终点处初始血量减去消耗之后,一定要保证至少是1才行。

152. Maximum Product Subarray

题意:此题求连续子数组中乘积最大的。

:动态规划,此题不同之处在于,负数乘以负数得出正数,也就是说,一个最小的负数可能逆袭成最大的数。因此,在子问题中,我们记录以下标i为结束的当前最大数和最小数(负数)。

那么下一个下标的最大数是,前一个最大数乘以自己、前一个最小数乘以自己、以及自己三者之间最大的那个。同理,最小数是三者中最小的那个。一遍扫描完之后,记录下当前最大的乘积作为结果返回。注意的是,更新最大值会影响最大值的值,所以使用副本来存下前一个值,以便后来使用。

674. Longest Continuous Increasing Subsequence

题意:寻找最长增长的substring。

:此题使用动态规划。每次发现比前面一个数大的时候,局部最大从1开始即可。 可以优化空间O(N)到 O(1)。

377. Combination Sum IV

题意:此题相比于39题,更加多的限制,也就是全是正数,且不含重复元素,元素可以多次使用,求等于正数target的组合。序列不同,例如[1,1,2]和[2,1,1]不算重复的。另外,结果只需要组合的数量,而不需要具体列出组合。

:此题如果使用常规的dfs,但是此题由于可以选自己,所以必须要排序。但是dfs方法会超时,试想一个[1,2,3],能组成100的组合实在是太多了,递归必然造成大量重复计算。所以使用动态规划。

由于[1,1,2]和[2,1,1]不一样,那么此题和爬梯子题一样(就是每一步可以走1,2或者3步,然后问爬完梯子有多少种方法)。

问题递归的变为,到达target最后一步是通过几种元素,也就是问题递归为target减去最后一个元素的子问题,且是这些子问题答案的总和。

两种方法:一个是topdown,也就是记忆化搜索。

一种是bottom up,从1计算到target,只要期间一个数大于任何一个元素,那么就加上,即dp[i] += dp[i - num] if i >= num。

理解和记忆:爬梯子里面是从前一步过来或者从前前一步过来,对应此题就是,for循环nums数组,能从一个num过来就过来,不然就拉倒。

PS.(1) target为0的组合数是1,而不是0。意思是全不选的情况。

(2) 可以先排序,然后在num比i小的时候,后面的num全部不用考虑,直接break。

(3)如果[1,1,2]和[2,1,1]算重复,那么就是二维背包问题。

由于是一个数可选多次,像是一维背包。

322. Coin Change

题意:找零钱,求最少组合硬币数,也就是问最少找多少枚硬币。

:解决target大小的问题,那么可以先解决所有target - nums[i]的子问题,然后选择其中最小的子问题加1来作为自己的答案。

要注意此题可能会无解,如果是面额不合适,是会出现的,此时应该返回-1。

518. Coin Change 2

题意:此题是求找零钱硬币组合数,和377题唯一区别是:[1,1,2]和[2,1,1]算重复。

:本质是完全背包。完全背包就是物品选择方式不是01的,而是次数不受限制。他与01的计算时候区别在于,对于一个物品i,考虑不是不选和选择一次,而是来自于不选或者选1次,选2次…

完全背包中,第二维的每个元素分别是以0开始并以i下标为结束的集合,相当于每次比之前多考虑一个新加入的元素。

这样每一步当前物品的选择都是基于之前的元素的所有选择情况决定的,也就是说,先考虑1,再考虑2,就避免了出现[1,2]和[2,1]这种重复的情况。

二维背包的第二维度按集合从小到大考虑,本质就是告诉物品之间的选择先的后顺序是需要考虑的。

物品可以重复选,那么递推公式里面,target除了依赖上面不选过来的,而且要依赖同一层之前计算的多个结果(也就是依赖上方格子、左上方若干个格子以及左边若干格子,其中左边格子的值已经包含了左上的格子的解,所以可以直接依赖左边的格子)。

理解:到当前amount,考虑选择物品i的时候,由于可以重复选,所以不仅仅是amount - nums[j]一个,还存在amount - 2* num[j], amount - 3*nums[j],…直到amount - k * nums[j] < 0为止。

与01背包比较:01背包不可重复选的时候,依赖的是不选和之前一层只选一次过来的,也就是依赖正上方一个格子和左上方一个格子,一共依赖两个格子。

如果是优化二维空间到一维,那么循环要变反为n从大到小循环,因为要利用。

PS.解和377几乎一样,但是看起来两个循环嵌套是反过来的。 也就是说,不是考虑倒数第二步是怎么过来的,而是对每一个硬币,考虑大于等于该硬币的amount的贡献,也就是说一个硬币只会被考虑一次。也就是说对于硬币2,我们考虑他对2到amount的贡献,对于3考虑他对3到amount的贡献,而之前的题目解法是反的,也就是amount == 3的时候,又会把硬币2重复考虑一遍。 对于amount=4,考虑过1对4的贡献了,就是[1,1,1,1],[1,1,2]。后面从2开始考虑的时候,不能用1这个硬币了,如果用了就会产生[2,1,1]这种重复元素。 先使用coins做外重循环,表示一次只考虑一种硬币。

221. Maximal Square

题意:给出只包含0和1的二维矩阵,求实心1的正方形中最大的面积。

:此题使用动态规划。思路是:dp[i][j]代表以坐标(i,j)必以右下角结尾的最大实心1正方形的size大小。

那么:dp[i][j] 在matrix[i][j]==0的情况下等于0,如果matrix[i][j]==1,那么看dp[i-1][j-1], dp[i-1][j]和dp[i][j-1]三个中最小的+1。这一点说明了二维矩阵动态规划题的一个通用思路,那就是考虑临近结点(不止一个,多数情况下是三个)作为子问题被解决后对当前格子的贡献。结果就是最大的dp[i][j]的平方。

PS.初始化时候,需要初始化第一行和第一列,因为他们能仅凭自己本身元素断定是0还是1。之后沿着从左到右,从上到下的扫描顺序就可以自然的求解出所有dp[i][j]。 可以使用滚动数组优化空间,此题依赖左边、左上、上边三个格子,不能使用之前的滚动数组(之前滚动数组使用一个一维空间就可以)解决法,应该使用两个一维空间,交替使用一维空间就可以了。

673. Number of Longest Increasing Subsequence

题意:求解最长subsequence的个数。

:此题是经典的求最长subsequence的follow up。

解决方法是,在每次更新最长subsequence的时候,也要同时更新到达此节点最优的路径个数:dp[i] == dp[j] + 1的情况下到达i节点长度的路径数累加到达j结点的路径数。相反,如果是dp[i] < dp[j] + 1,那么路径数被置为j结点的路径数。

还有一个关键的地方要注意:等于最长路径长度结尾的点不是一个,而是有若干个,这样要把所有的满足条件点的路径加起来得出最终答案。

764. Largest Plus Sign

题意:给出二维全1的01矩阵,然后又给出其中坐标为0的数组,问其中最大的十字半径是多大。

:此题解法是对于每个位置,如果是1,那么查看以该位置为十字中心能够延展到多大的十字,也就是向左、向右、向上、向下延展的连续1中最短的那个。如果使用暴力求解,那么显然复杂度是O(n^2 * n)。

使用动态规划,可以把复杂度降为O(n^2)。降时间的方法就是对一个方向可以O(n)时间求出所有延展,例如,向左延展,如果为0,那么对应的左延展为0,要不然就是前一个的左延展加1。同理求出另外四个方向的1延展。只需要两边扫描计算出四个方向延展,一遍是从左向右,从上向下扫描计算出右延展和下延展;第二遍是从右向左,从下向上扫描得出左延展和上延展。这样,最后在扫描一遍,看四个延展方向中最小的中最大的,作为答案。

上面方法需要O(4 * n^2)的空间复杂度。空间复杂度可以减少。其实,我们只关心四个方向中最小的那个,也就是说,只需要使用一个n^2的空间保留最终的结果,四个方向扫描过程中,只需要使用4个临时变量,然后如果该变量比最终结果小就更新(结果数组初始化为n)。扫描过程需要分开计算,不能两个双重循环得出答案,而是需要4个双重循环计算出四个方向的答案。

416. Partition Equal Subset Sum

题意:求正整数数组是否能分成两个相等的部分。

:此题是0-1背包问题,因为原问题可以转化为能否挑选出元素,和等于数组总和的一半。

0-1背包问题的解法套路就是:对于dp[i][j]表示集合{0,1,2,…,i}和target为j的子问题,且最后一件物品考虑i,所以只要考虑dp[i-1][j]以及dp[i-1][j - nums[i]]。最终结果就是dp[nums.size()][target],表示从集合{0,1,2,…,n}中选,选出target的问题。

此题来说dp数组是bool型,表示能否找到和等于target。注意的是,具体实现的时候,要在最前面的列和行之前加一个辅助列/行。

还可以使用滚动数组来减少空间使用,因为dp[i][j]依赖于dp[i-1][j]以及dp[i-1][j - nums[i]],也就是说,完全依赖于上一层的两个元素,而且我们不能正序(0到size)计算,因为正序计算后,依赖的两个元素中的前一个已经不在是上一层的结果了,而是最新一层的结果,所以要倒着计算(size到0)。

494. Target Sum

题意:给一个正整数数组,每个数字之前加上正负号,结果等于target,求方案个数。

:方法一:暴力求解:使用dfs,每次进入一层,无需记录path,只需要把当前层的两个结果转换为下一层,在看最后一层时候,看得出的结果是不是target来判断该路径是否走的通,走的通就加1。

方法二:使用动态规划。 dp[target][i]表示现在题目问题规模是可以变化的,也就是说,target是可变的,i表示i个整数元素的片段,也就是只能使用前i个元素,也就是说,任何一个dp[target][i]都是一个类似的问题,不过规模更小,他不是大问题的一个步骤,而是一个类似的问题,只不过规模更小。 、优化: sum(P) - sum(N) = target sum(P) + sum(N) = sum(nums) => 2 * sum(P) = target + sum(nums) 其中sum(P)表示加正号数集合的和,sum(N)表示加负号的集合的和(取正)。所以存在上面两步的转化。结果就是将原来的问题转化为combinationIV类似问题。另外如果target + sum(nums)为奇数的话结果直接返回0。 从代码来看,滚动数组后的结果和combinationIV相似,但是i要倒着计算。这样保证了每个元素只能对最终的target做出一次不累加的贡献。

309. Best Time to Buy and Sell Stock with Cooldown

题意:对一个数组,数组元素表示当天股票价值,现在求最大利润,只不过:(1)当天只能买或卖,而且只能先买入后卖出,不能一直卖。

(2)卖股票之后,要等一天才能买

:此题是比较特殊的和经典的动态规划题。与一般动态规划不同,此题每个具备多种状态。

所以动态规划方程要使用三个状态:hold,sold,rest,分别表示下标为i的子问题所处的状态,hold表示在第i天持有股票的情况,sold表示在第i天当天卖出股票的状态,rest表示之前某一天卖出股票,至今还没有出手买股票的状态。 看第i-1天状态和第i天状态之间的转换关系:hold可以通过卖到sold,sold状态不可以通过买直接到hold,而是要必须经过当天的冷冻操作到达rest状态,而rest可以通过买到hold状态,同时rest也可以通过空操作到自己。另外要注意的是hold也可以通过当天空操作到自己,sold不能通过空操作到自己,而且rest不能通过卖到sold,因为必须要先买才能卖。 这么来看,sold只是进行cooldown操作的一个临时状态,rest才是真正”hold”的状态。 那么现在我们来看三个方程之间的规律: (1)hold[i] = max(rest[i-1] - prices[i], hold[i-1]),前面已经分析了,hold状态只能是从上一步的hold状态当天空操作转化过来,或者是上一步rest状态通过当天买转化过来。 (2) sold[i] = hold[i-1] + prices[i],同理,sold状态只能是上一步状态时hold时候通过sell转化过来。 (3) rest[i] = max(sold[i-1], rest[i-1]) 现在考虑三种状态的初始情况。第一天hold[0]=-prices[0],sold[0]=0,rest[0]=0,因为第一天要是hold必须通过买进,消耗了prices[0],相反应该是无法卖出,所以初始化为0。

也可以进一步优化,把空间复杂度降到O(1)。也就是说,只重复使用三个变量即可。

714. Best Time to Buy and Sell Stock with Transaction Fee

题意:此题与309不同之处在于,不需要冷冻,但是每次购卖的时候需要交交易费。

:此题还是使用309的方法,这次的状态只有hold和sold,hold和sold之间相互转化,hold和sold也可以分别指向自己。记住sold时候要考虑fee。结果是sold[size-1],因为最后一次只能卖出股票,让自己处于sold状态。

678. Valid Parenthesis String

题意:括号匹配,括号只有”()”一种,但是存在*,可以代表’(‘, ‘)’或空。

:此题解法多样。 方法一:动态规划+记忆化搜索。dp[i][j]表示从下标i到下标j的区间内的串是有效的,还是无效的。

情况1:如果i==j,那么看str[i]是不是等于”*“,如果等于则为true,否则为false。

情况2:如果i和j不等,且i和j之间是相邻的,也就是j-i == 1。我们看s[i]和s[j]是否匹配,即是不是这几种情况:”()”, “*)”, “(*”, “**“,如果都不是,那么返回false,否则返回true。

情况3:如果i和j不等,且i和j之间相差大于1,那么看dp[i][k]和dp[k+1][j](其中k >= i && k < j)两者是不是都为true,如果存在一个都是,则返回true,如果一个都找不到,那么返回false。

此方法时间复杂度是O(n^3),因为每两个下标都会处理n的时间。属于暴力求解。

方法二:观察下面几种情况:”**”, “*)”, “*(“。我们发现,只有第三种的 “(“是无效的。

使用两个栈,一个栈存储左括号’(‘的下标,另一个栈存储’*‘的下标。这样,扫描时候当遇到’*‘或者’(‘,那么先分别压入对应的栈。遇到右括号时候,尝试匹配,如果失败则返回false。

匹配右括号的时候,先尝试从左括号栈进行弹出,因为在两个栈都存在元素时候,情况无非是”*(“、”(*“,其中无论哪一种情况,都可以使用’(‘和当前’)’进行匹配消除,因为*可以作为空来看。如果是left栈没有,那么使用star栈的*来抵消,如果star栈也没有,说明匹配不上,直接返回false。

右括号匹配完了,接下来来分析剩余的左括号和”*“之间的关系是否合法:把剩余的”*“当做“)”或者空来看与左括号进行消除。

最终我们看两个栈的情况,如果left栈顶的值比star栈顶的值大,说明出现了”*(“的情况,也就是说,想消掉此”(“已经不可能了,返回false。

反之,两个栈都弹出值,把剩余的”*“当做“)”,最后我们看左栈是否为空,如果不为空,那么说明消不掉,返回false。否则返回true。如果最后剩余的是star栈,那么无所谓。

10. Regular Expression Matching

题意:给出两个串,一个串s是字母构成的,一个串p是除了字母以外还包含’*‘和’.’的,’.’匹配任意一个字母,’*‘可以表示之前一个字母可以出现0次或者多次。现在求s和p是否能匹配。s和p的长度不一定相等。 匹配的例子: isMatch(“aa”,”a”) → false

isMatch(“aa”,”aa”) → true

isMatch(“aaa”,”aa”) → false

isMatch(“aa”, “a*”) → true

isMatch(“aa”, “.*”) → true

isMatch(“ab”, “.*”) → true

isMatch(“aab”, “c*a*b”) → true

理解:p串中不存在**这种情况。

:此题使用动态规划来解。可以列一个表格,纵向为s串,横向为p串。dp[i][j]表示s串中下标0到i的子串和p串中下标0到j的子串之间是否匹配。 那么我们来考虑p[i]和p[j],(1)如果s[i] == p[j],那么dp[i][j] = dp[i-1][j-1]。

(2) p[j] == ‘.’,虽然p[i]不等于p[j],但是’.’可以匹配任意一个字母,所以dp[i][j] = dp[i-1][j-1]。

(3) p[j] == ‘*‘,此时看p[j - 1]和s[i]的关系,(a)如果不等,那么dp[i][j] = dp[i][j-2],也就是说我们把j-1处和j处的*一起当作空字符(0次)来处理。

(b) 如果p[j - 1] == s[i]或者p[j - 1] == ‘.’,那么可以是把j-1处和j处的*一起当作空字符来处理, 也就是dp[i][j] = dp[i][j-2]。

也可以是把j-1处和j处的*一起当作两个以上j-1处的字符来处理,此时dp[i][j] = dp[i-1][j],因为可以匹配上。也可以是把j-1处和j处的*一起当作一个j-1处的字符来处理,此时dp[i][j] = dp[i][j-1]。

(4) p[j] != s[i]且p[j]是一个普通字符,此时匹配不上,dp[i][j]=false。

初始化条件是:i = 0的时候,表示s串为空,那么看p串0到pLen的考虑,如果p[j]为’*‘,那么dp[0][j] = dp[0][j - 2],否则dp[0][j]为false。dp[0][0] = true。

44. Wildcard Matching

题意:此题和第10题区别在于使用’?’来匹配任意字符,不是使用’*‘扩充任何前缀字符,而是作为任意长度的某个字符的串,也可以为空。结果必须是完全匹配的。”aab”, “c*a*b”在第10题中是true的,但是此时为false,因为*不能消除之前的c字符。另外*并不是扩充之前的字符,而是可以是任意字符。 isMatch(“aa”,”a”) → false

isMatch(“aa”,”aa”) → true

isMatch(“aaa”,”aa”) → false

isMatch(“aa”, “*”) → true

isMatch(“aa”, “a*”) → true

isMatch(“ab”, “?*”) → true

isMatch(“aab”, “c*a*b”) → false

:方法与第10题是相同的。先看s[i]和p[j],如果相等,那么dp[i][j] = dp[i-1][j-1],

如果不等,但是p[j] == ‘?’,那么也是dp[i][j] = dp[i-1][j-1]。如果p[j] == ‘*‘,那么,可以把*看做是空,此时dp[i][j] = dp[i][j-1]。也可以把*当作等于s[i],此时dp[i][j] = dp[i-1][j-1]。也可以把*看做两个(多个)s[i],尽管s[i- 1]可能不等于p[i - 1],因为*可以匹配任何串,此时p[i][j] = dp[i-1][j]。

689. Maximum Sum of 3 Non-Overlapping Subarrays

题意:给出一个数组,给出大小k,求出数组中不重叠的3段长度大小为k的区间,3段的和加起来最大。

:posLeft[i]表示区间[0, i]的以i为最后下标的最大长度为k的一段interval的最右下标。

posRight[i]表示区间[i, n - 1]的以i为起点到数组末尾的最大长度为k的一段interval的最左下标。

其中i的范围是[k, n - 2k]。因为区间长度至少是k,那么posLeft[i]一定要从k开始,而posRight[i]一定从n - k往前计算。

所以中间区间的起点选择就是[k, n - 2k]。因为中间区间只能从k开始,或者从n - 2k开始。

先计算posLeft[i]和posRight[i]。计算完之后,考虑每一个中间区间的起始位置。

如果posLeft[i-1]对应的最大值和[i, i + k]的区间和,以及pos[i + k]组成的和最大,那么就更新起点下标三元组为(posLeft[i-1], i, posRight[i+k])。

265. Paint House II

题意:n个房子,k种颜色,cost[n][k]矩阵表示为某个房子上第k种色的代价。求给全部房子上色的最小代价,且房子之间不能涂一个颜色。

:此题区别于I的是有k种颜色,但是当前选颜色时候,只需要考虑之前两个最小值就可以了。

对每一个房子每一种颜色进行考虑,当前房子上色时候,看之前房子选颜色的最小代价和次小代价,如果当前选的颜色和之前最小代价是一个颜色,那么就选次小的,否则选之前代价最小的。当前层计算时候,也要得出自己的最小值和第二小的值供下一层使用。

PS.此题技巧一个是如何保存上一次的两个变量,另一个是如何更新最小的两个值(技巧就是更新最小值时候要把当前最小值赋值给第二最小值)。

276. Paint Fence

题意:给篱笆上色,n个篱笆,k种颜色。不能出现连续三种颜色的房子,求给篱笆上色的种数。

:此题仍然是动态规划题目。考虑以第i个篱笆为结尾的子问题。

分两种情况:一种是第i个篱笆和第i-1个篱笆颜色相同,那么dp[i] = dp[i - 2] * (k - 1),也就是问题缩减为以i-2为下标的情况乘上最后两个选一种颜色的情况数,也就是k-1。

另一种是i个篱笆和第i-1个篱笆颜色不相同,那么只需要考虑第i下标处的颜色选择,dp[i] = dp[i - 1]* (k - 1)。

两种情况之间不冲突,因此要加起来。得出dp[i] = dp[i - 2] * (k - 1) + dp[i - 1]* (k - 1)。

分析初始情况:当只有一个篱笆的时候,篱笆上色有k种;当有两个篱笆的时候,如果两个篱笆颜色一样,那么有k种选择,如果两个篱笆颜色不一样,有k*(k-1)种选择,总共有k*k种选择。

368. Largest Divisible Subset

题意:给出一个装满了正数且不含重复元素的数组,现在求出最大子集,要求这个子集中的两两元素都满足Si % Sj == 0或者 Sj % Si == 0. 例如:1,2,4,8就是满足这种条件。

:解题关键是看出来每次选新元素,都是要与之前比它小的元素进行余,因为只有正数,所以小余大永远不为0,大余小才有意义;

另外,我们观察1,2,4,8的规律,规律就是,只需要余之前的较小数为0就可以了,因为一定比。同时又要联想到最长子串的那种与之前所有元素比较,看看满不满足条件。至此,我们知道此题大致思路是排序+dp。剩下的一个问题是不仅要知道长度,也要知道具体数字。

解决方法就是,维持一个parent数组,记录最大值是从之前哪个元素更新而来。

790. Domino and Tromino Tiling

题意:2xN的矩阵用两种骨牌铺满的情况数。

:此题是dp,dp题目一定要先列1,2,3,4的基本情况,看递推公式,计算正确的公式是难的,最终编码是简单的。

参考http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-790-domino-and-tromino-tiling/。

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1+dpn-3

还是按照骨牌有突出来理解比较好。这么理解的本质还是递归,把问题末尾填上几种不同情况,那么问题的规模就会缩减。

dp[i][j]表示长度为i(两行长度最小值),末尾形状为j的拼接方法总数,j = 0表示末尾没有多余部分,j=1表示第一行突出一个,j=2表示第二行突出一个。那么推导公式为:

dp[i][0] = dp[i - 1][0] + dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][0]

dp[i][1] = dp[i - 1][0] + dp[i -1][2]

dp[i][2] = dp[i - 1][0] + dp[i -1][1]

注意计算起始值: 如果是按突出那一列i的来算,那么起始值是dp1[1] = dp2[1] =dp3[1] = 1; dp1[2] = dp2[2] = dp3[2] = 2。等于2的意思是,要么是三角的自己,要么是一个横的。

如果是按突出一列的前面一列来算,就是dp1[0] = dp1[1] = dp2[1] = dp3[1] = 1。

474. Ones and Zeroes

题意:给出一个0,1串的数组,然后给出总的0,1数,问最多可以构造数组中多少个串(有消耗)。例如{“10”, “0”, “1”}, 给出1的个数m=1, 0的个数n=1。虽然1个1,1个0可以构造出其中任何一个串,但是在有消耗的情况下,构造出后面的 “0”, “1”是最优选择,也就是可以构造出两个串。

:此题两种思路:一种是dfs,一种是dp。在不要求计算路径的情况下,使用dp。怎么理解呢?dfs的话,此题相当于是计算集合的题目:对于数组中一个元素,有选和不选两种情况,这样只要dfs回溯的搜索一遍,就可以得出答案。

对于dp来理解,就是相当于01背包问题、相当于二维的选n个点和加起来等于target点,也就是说使用dfs和dp都能解的原因在于此题本质上是递归解法,使用dp的原因是避免大量的重复计算。

808. Soup Servings

题意:给出初始值对(NA, NB),有四种方式等概率来消耗原始值,现在求NA先消耗掉的概率。

:此题是动态规划,但是解题的关键还是在于递归,如果0.25的概率选择某一个方向,发现剩余的A小于等于0,那么返回1的概率给上一层,如果A,B同时小于0,那么返回0.5的概率给上一层。此题还有一个坑在于dp数组大小有限,所以初始传入的N要做大小等比例修改。

375. Guess Number Higher or Lower II

题意:给出一个1到n的数,然后让你猜,每次会告诉猜高了还是猜低了,不过每次都要支付猜的那么多钱,现在问要支付最少多少钱可以一定猜的到该数。

:此题一开始陷入二分搜索的思路,但是很明显,二分只是一种方法,而不是总体思考解决这个问题。此题其实是动态规划题。设dp[i][j]表示在数字i到数字j中猜,最少多少钱能保证猜的到。

那么如果猜x,x是介于i到j的数,那么需要花x + max (dp[i][x - 1], dp[x+1][j])的钱,此处使用max的原因是我们不能提前知道猜x后是猜高还是猜低,所以每次应该用最坏情况保证最少钱的条件。

那么我们知道:dp[i][j] = min (x + max (dp[i][x - 1], dp[x+1][j]), x介于i到j。也就是我们考虑猜每个数,由于动态规划,所以我门可以选择其中的花费最小的那个。使用记忆化搜索就可以计算出结果。

813. Largest Sum of Averages

题意:将数组分为k份,顺序不变,求使得每段平均数和最大为多少。

:此题是动态规划,一开始以为是三维动态规划dp[i][j][k],但是此题只需要二维dp[i][k]就可以,如果分为三维,那么会出现重复考虑,例如前面一段分一段,后面一段分两段实际上和前面一段分两段后面一段分一段是等价的情况。

所以,固定一个端点,例如只考虑0到下标i切成k段的最大平均和。

294. Flip Game II

题意:翻转连续的++为–,直到对手没得选,自己就赢了。

:此题一开始以为是动态规划,总觉得在自己可选的几个选项中也许有最佳的选择。

实际上应该这么考虑:自己把每一步可能的都走一遍,如果自己走完之后,对手也是相同策略尽可能的获胜,那么只要自己走的所有可能情况中只要有一种是对手是失败了,那自己就一定能成功。

所以此题是dfs回溯加上记录中间结果。

562. Longest Line of Consecutive One in Matrix

题意:求矩阵中上下、双对角线连续的最长的1。

:使用三维动态规划,dp[i][j][4]表示,下标i,j为结尾的最长的连续的1。

使用常规的自上而下,从左到右的扫描,因为dp[i][j][4]只依赖左边,上边,左上边,右上边的格子。

361. Bomb Enemy

题意:给出二维矩阵,0的地方可以放入炸弹,炸弹可以炸所在行和列(但是不能越过墙),W表示墙,E表示敌人,所以题目问的是在哪个0放入炸弹可以炸最多的敌人。

:此题就是暴力求解,

方法一:准备4个二维数组,分别表示该位置上下左右分别有多少个E。然后,正着扫描一遍二维数组,根据左和上的信息更新当前信息。倒着扫描一遍二维数组,根据下和右的信息更新当前信息。然后在扫描一遍,把0所在的地方上下左右结果加起来就是当前坐标可以消灭的E数,扫描完就知道是哪个坐标可以消灭最多E。PS.正反扫描时候,会出现越界问题,第一行,第一列,最后一行,最后一列都要单独处理。

方法二:考虑的基点是从i = 0   j = 0处,或者遇到左侧或者上方是W时候,就单独起一个循环,把此行此列剩下的E元素计算一下,然后遇到0时候,就看能不能更新下最大值。也就是说,只求当前遇到0之前的解,但是解遇到W时候会失效,失效的时候要重新计算。

PS.核心计算就是计算当前位置左侧(右、上、下)到当前位置为止有多少个字符‘E’。

552. Student Attendance Record II

题意:第I题是验证是否可以得奖,此题是只给出串的长度n,要求把所有可以得奖的情况列出来,得奖的情况就是串没有多余一个的A,也不能出现连续的三个L。

:此题有一种非常巧妙的动态规划解法:将A和非A单独考虑,那么我们发现,对于长度为k的问题来说,A由于不超过一个,那么如果选A,那么A可以出现在任何一个位置,剩余的部分就是两个非A的情况,另外如果不选A,那么整个串就是非A的情况。

再来考虑非A的情况,非A的情况下,就是一维dp,考虑结尾,如果是以P结尾,那么dp[i] = dp[i - 1];如果以L结尾,那么要看之前是什么结尾,发现只有LLL这种结尾是不合法以外,其余结尾都满足dp[i] = dp[i - 1]的需求,所以我们得出递归公式是dp[i] = 2 * dp[i - 1] - dp[i - 4]。

再来考虑边界情况:如果n比4小,那么就需要直接计算了,由于前4个都是直接计算的,因此在一开始申请数组的时候,如果n比4小,那么至少要分配4个空格。

另外一个问题是结果太大要模M,那么在c++的时候,对负数求模,要先让负数加一个M,然后在使用%来模M。

568. Maximum Vacation Days

题意:给出nxn矩阵flight表示城市i到j的是否有航班,也就是城市路线图的邻接矩阵,然后又给出nxk矩阵days,表示城市i可以在第j周休息多少天的邻接矩阵,现在要求最大可以休息多少天。 第一天必须从城市0出发,一共有k周。

:此题是动态规划解的题,但是总的思路似乎可以使用不带visited数组的dfs(泛洪??),从第i个城市出发,下一个城市可选的范围是它的邻居,然后当前对应的层就是所在的周,然后从全部的最后一周的结果选最小的那个,就是答案。此题的意思似乎不是每个城市只能待一次,而是条件允许可以待多次。这样纯dfs的时间复杂度是n ^ k。

画一个搜索树图就知道,下面的层中存在大量重复,重复就是指,第j周出现在第i个城市这种相同分支。

所以,一个方法是使用记忆化搜索,使用dp[i][j]来记录已经搜索过的结果,表示有j周从城市i出发能休假的最多天数,这样能减少大量重复。

再来看自底向上的解法。相比于自顶向下,该方法的好处是,可以使用滚动数组来使得空间复杂度降低到O(n)。来看下递推公式:dp[i][j] = max (dp[i - 1][x] + days[j][i]),其中x介于0到n-1,且可以从城市x到城市j。

其中的i,j与之前定义相反,i表示周,j表示城市,i从k开始到1(反过来的原因是之前结果是不能重复累加的,也就是说如果从1到k,那么之前的值会被累加起来,实际上是不需要的),对于每一周遍历一遍所有航线,看能不能更新dp[i][j]。由于i只与i-1有关,所以可以使用滚动数组来优化空间。

72. Edit Distance

题意:通过增加一个字符,减少一个字符,修改一个字符把串s变成串p,请问最少需要多少步。

:dp[i][j]表示s.substr(0, i)到p.substr(0, j)的最小步骤,“到”的意思就是说将串s.substr(0, i)变为串p.substr(0, j)。列出二维矩阵,每个格子只依赖与左上角,左,上的三个格子。

583. Delete Operation for Two Strings

题意:给出串S和T,允许删单词,求最少的删除步数,使得两串相等。

:思路一:此题和求两个串的公共子序列本质是一样的,只需要先使用dp求出公共子序列长度,在将两串总长度减去该值的两倍得出答案。dp[i][j]表示第一个串i结尾与第二个串j结尾的公共子序列,这样我们知道,如果s[i]==p[j],那么dp[i][j] = dp[i - 1][j - 1] + 1,否则dp[i][j] = max (dp[i-1][j], dp[i][j -1])。

思路二:此题和72 Edit Distance题解题方法一样,只不过只有一种删除操作。

注意的是:如果word1[i - 1] != word2[i - 2]时候,dp[i][j]仍然可以从dp[i - 1][j - 1]推导:也就是dp[i][j] = dp[i - 1][j - 1] + 2。

486. Predict the Winner

题意:给出整数数组,总和不大于int表示范围,现在两个人从里面取数字,只能从开头或者结尾取,最后取出总数最大的那个人获胜。现在问先手能不能一定赢。

:博弈类dp,dp[i][j]表示从区间[i, j]里玩游戏时候,先手能取出来的数字总和。此题难点在于,自己两种中做出选择之后,变成了对方先手,所以,下一步是对方先手的子问题。这样,要进一步考虑,也就是对手下一步的情况,其中难的地方在于对手的选择的数字自己是不能再选的,自己只能从对手给自己剩余的两个区间中继续选,也就是意味着对手一定会留下较小区间的给自己,也就是说不关心对手当前选的值具体指有多大,因为对手留较小区间给自己必然是全局最优的:也就是说当前值选的结果就是做局,做的是剩余区间的值较小的局。

PS.如果是数组包含的元素是偶数个,那么先手一定获胜,只要把奇数位和偶数位的和算一遍,按照较大的走就会赢,因为总能取到所有奇数位或者所有偶数位。

博弈类dp特点就是,第一层结果要看第三层的,且每一层可以决定下一层的走向。第三层的结果虽然是自己先手,但是对手可以选择让自己选最差的,因此,在第三层里面必须全胜(或者选最差的),败一个都不行,在第二层中只要一个胜利(或者选最大的)就可以胜利。

画博弈树的时候,第三层最好是base case,这样输赢一目了然。

312. Burst Balloons

题意:给一个数组,里面是气球,打爆一个气球可以得到左边气球和当前气球以及右边气球的乘积,打完之后临近气球自动变化,求打出的总和最大多少。两个边界部分默认算1。

:此题正方向想的话,就是打爆一个气球后,看剩余的子问题,这样的话,发现区间型没法做,只能使用dfs来一个个情况枚举,但是这样时间复杂度是排序的复杂度O(n!)。

但是反方向想,就可以得出O(n^2)的区间型dp的解。反方向想就是看n个气球中最后打爆哪个,这样发现最后打爆的气球的左边右边是互不干扰的子问题(因为两个区间必然会以最后被打爆的点做区间边界),然后在加上最后打爆的气球的乘以当前总区间之外的边界就得出打爆一个气球的情况。最终答案是所有情况中最小的。

727. Minimum Window Subsequence

题意:给出S串和T串,要求S的子串W,T是W的子序列,求最短的W。

:暴力解法思路就是:对于每一个和T串开头相同的字符开始,向后找最小包含的substring,然后取出最短的一个作为答案,其中可以做出一些优化,但是时间复杂度总的来说还是O(len(S) ^ 2 * len(T))。

此题其实可以想到是与大串小串之间的公共子序列问题类似,也就是串串之间比较的dp题型。所用dp来解:dp[i][j]表示串T中0到i的子串T’和S串中0到j串S’作为子问题解的时候,其中T’的匹配上的子串(也就是包含S’作为子序列)的最靠左的起始下标。

这样,在S[i] == T[j]的时候,dp[i][j] = dp[i - 1][j - 1],问题退化成前一步的最靠右的结果,且当前的i,j也是最右边的相等,所以最靠右的结果不变。

S[i] != T[j]的时候,dp[i][j] = dp[i - 1][j],此时最后一个字符不等,说明问题可以退化成T不变,S前一步的结果。

如果匹配不上,那么dp[i][j] == -1。

编程时候,比较难考虑的点,一个是初始情况:T串为“”的时候,S串的考虑是:S’串中的子串只有“”才能包含“”,但是正常下标往后取子串总是存在字符的,满足不了“”,所以此时起始下标就是S‘串的末尾下一个位置。

另外一点,就是答案蕴含在所有的dp[i][j]的最后一列,也就是T的长度固定,S变长的所有情况中,选择长度的最小的作为最终的答案。

还可以使用改进的双指针解法,类似于KMP。

471. Encode String with Shortest Length

题意:把字符串压缩成最短的k[encoded_string]形式。

:动态规划,dp[i][j]表示可以把s中下标i到j压缩成最短的形式(k[encoded_string]或原串)。

然后发现,dp[i][j] = min {dp[i][j], dp[i][x] + dp[x+1][j]}。其中还要与s[i, j]的子串t直接压缩后进行比较,直接压缩的技巧就是在t + t中从第一个位置开始查找t,如果发现只能在中间位置找到,那么说明t不可压缩,否则就说明t是可以压缩的。如果压缩不了,那么看中间切割方式与原串之间哪个长度最小,选小的。

403. Frog Jump

题意:给出石头坐标数组,青蛙从坐标0开始,如果能过河,那么返回true。规则就是青蛙只能从石头之间跳,而且每次跳之后,下一步只能跳是上一步长度k的k - 1, k+1或者是k的距离。

:此题显然是动态规划,此题特殊之处在于每一步还是根据前一步的状态来看,所以应该加上之前走一步距离这个维度,所以此题就是二维的记忆化搜索。初始条件就是k=0。

二维记忆化搜索使用hashmap的技巧就是:一个hashmap里面的值是另一个hashmap。

1400. Fermat Point Of Graphs(lintcode)

题意:此题是求无环无向图中,距离其他所有结点总和最小的结点。

:此题关键是无向无环图,所以图其实是树结构。那么可以使用非dijktra来解题,对于每个root起点使用dfs来计算到其他节点距离,然后只需要O(n)的时间计算一个点距离其他点的距离,同时总距离也计算出来了,这样总的时间复杂度是O(n^2)。

可以进一步优化,找规律,发现,每一条边为总距离贡献的距离,其实是边导致分支的子树结点数量的倍数,也就是分支之后的路径数。这也意味着计算方式变成动态规划:设dp[i]代表以i为根子树的总距离,那么我们知道dp[i] = dp[j] + e(i, j) * cnt[j], 其中j为i的所有子节点, cnt[j]表示j结点为根的子树结点数量。

最难理解的就是之后的第二步:在保持之前的树结构不变的情况下(也就是与之前dfs起点一样),在进行一遍dfs,这一遍的dfs是计算每一个点到其他任何结点的总距离。对于结点i来说,dp[i]意味着以i为根节点的子树的距离总和,那么接下来要计算的就是i到它的所有祖先结点,以及兄弟结点的距离总和。如何计算呢?

利用数学公式。之前一步的dfs已经计算出了根到所有结点的总距离sum,来看sum - dp[j] - e(i, j) * cnt[j],意思就是根节点到i以及除了i的j分支以外的结点距离总和; (n - cnt[j]) ) * e(i, j)意思就是边(i,j)对除了j为根子树的其他结点路径的贡献。这两部分加起来的意思,其实就是结点j到除了自己子节点外所有结点的总距离。

理解:也就是把结点j的父节点当作是子结点,第一个部分正好是父节点到除了自己分支以外结点的总距离和,然后在加上自己到父节点这条边对父节点作为子节点的情况下的贡献。注意,计算完之后,下一层新子结点计算时候,他们应该参考的是自己父节点到其他结点的总距离,也就是说sum需要进行更新操作。

1035.Uncrossed Lines

题意:给两个整数数组,数组里面相同数字间可以组队连线,线之间不能交叉,问最多连线可以有几个。

:此题规律就是,如果同一个位置是相同字母,那么必连,所以,规定dp[i][j]是数组A下标0-i和数组B下标0-j的解,那么,如果i和j所在字母相同,那么问题递归为dp[i - 1][j - 1] + 1;如果不等,那么问题递归为看i处字母在B数组的最接近且小于j的地方一样,就递归到那个子问题,同理,j处字母在A数组的最近的地方的子问题,两个子问题中的较大者。

在简化下,就可以发现,每次都是选最大值,因此,只要考虑dp[i-1][j]和dp[i][j-1]中的较大者就好了,没必要非得找到相同字母进行连线了。

再看基本情况:对于i和j同时为0时候,那么解看当前字母是不是相同,相同则是1,否则是0。

在仔细想想,发现,此题和求最长公共字序列是同样的问题。

279. Perfect Squares

题意:求出组成正数n的最少的平方和(1,2,4,…)。

:此题是动态规划,要求n,那么先求1到n-1,然后看从哪个过来数量比较小。和word break是一种类型的题。