所有代码详见：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的之前计算的结果 ，如何保证是01选择呢？答案是：选i的时候，结果是从上一层没有i的情况过来，也就是dp[i][j] = dp[i - 1][j - nums[i - 1]]，而不是dp[i][j] = dp[i][j - nums[i - 1]]。

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

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]表示0到i的最长回文串，但是发现dp[i + 1]不太好使用dp[i]，那么采用二维的思路： dp[i][j]表示下标i到下标j区间内最长的回文串。

考虑如何通过上一步结果，也就是dp[i + 1][j], dp[i][j - 1]和dp[i + 1][j - 1]，来构建dp[i][j]。

考虑的关键点是s[i]和s[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有关，画出二维数组:

注：二维数组的左下侧一半不需要，因为i <= j。（编码的时候，可以使用j = i, j < col-len, j++这种技巧） 基本情况：如果i == j， 那么dp[i][j] == 1。 最终结果：右上角的这个格子。

可知，一个格子依赖的是左边格子、下边格子以及左下边的格子。所以，编码时候循环顺序可以是： （1）按行扫描，从最后一行第一个元素开始，从左向右，从下向上； （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

题意：给你一个数组，每个元素表示一台洗衣机洗的衣服数量。然后现在每台机器可以一回合移动一件衣服到相邻的机器（也就选择向左或向右放一件， 衣服数量为0的洗衣机无法移动）。问最少需要几个回合后，可以让所有机器洗衣数量相等，也就是所有数组的值相等。如果做不到，那么返回-1。

解：首先，如果衣服数量总和余洗衣机的数量不为0，那么说明无法平衡，因此返回-1。其次，

把衣服数量当作波峰波谷来看，一个波峰如果从一个方向（例如向右）出发，平均每回合可以把自己的多余的1（比平均值多）传到右边任何一个点。例如[3,0,0,1]。3传给旁边的0，虽然旁边的0一开始是不能传的，但是0变1后就可以继续传给右边了，

所以说，例如3比最终平均值1大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)，每一步都用到之前计算结果。

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

或者这么理解，dp[i]表示元素0-i，且必须包含第i个元素作为最后一个元素的解，那么我们知道，最终答案一定是某个dp[i]。而dp[i]要么和i-1相连，要么就是自己单独作结果。

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

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。

看基本情况：dp[0]，那么看num[0]是否是1到9，如果是，那么dp[0] = 1，否则dp[0] = 0; 在看dp[1]，如果拆散了来看，其实情况非常复杂，01到09是0，10是1，11到19是2，20是1，21到26是2，26到29是2，30是1，… 但是实际上，需要这么考虑：如果num[1]是1到9，那么说明dp[1]至少和dp[0]一样，在来看num[0]和num[1]一起的组合是不是大于等于10，小于等于26，是的话说明dp[1]多了一个可能。

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]表示必须（0-i个房子的子问题）且必须选第i个房子为结束的解，最终答案是dp[i]里面最大的那个。

在看dp[i]， i - 1是不能选的，在看i - 2， 这里比较难考虑。实际上，i - 2不一定选，例如{2,1,1,2}，其中最后一个2如果选了第一个1，那么得不出最大值。

所以，正确的考虑是选dp[i - 2]和dp[i - 3]中的较大者（为什么不考虑dp[i - 4]? 因为房子价值都是正的，如果选dp[i - 4]，那么i - 4能够和 num[i - 2]结合，也就是说dp[i - 4] <= dp[i - 2]）。

总之，公式是dp[i] = max {dp[i-2], dp[i-3]} + nums[i]。

时间复杂度降为O（n）。接下来，还可以使用滚动数组来优化空间为O(1)。

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

PS. （1）如果存在负数，那么此题动态规划的思路与求连续最小子数组的和的模型是一样的，即局部最优和全局最优，dp[i]表示必须以i结尾的最大值，

dp[i] = max {dp[j]} + nums[i]，0 <= j < i - 1；

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

213. House Robber II

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

解：此题在198题基础上，尝试把圈拆成两个链，按198方法计算两次，选其中最大的。

如何拆分？拆成（1）不去第一个房子；（2）不去最后一个房子。例如 {1,2,3,4,5}拆成两个: {2,3,4,5}，{1,2,3,4}, 。

理解：（1）不去第一个房子{2,3,4,5}，并不代表一定去最后一个房子；不去最后一个房子同理。也就是两个房子都不去也可以，没问题。

（2）两种情况只是把同时选第一个房子和最后一个房子这种情况给去掉。

337. House Robber III

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

解：树的问题一般都想到使用分治法，

方法一：f(root)表示root的最大结果，那么有： f(root) = max(f(root.left) + f(root.right), f(root.left.left) + f(root.left.right) + f(root.right.left) + f(root.right.right) + root.val); 理解：选root，那么root.left和root.right不能选，结果等于f(root.left.left) + f(root.left.right) + f(root.right.left) + f(root.right.right) + root.val)； 不选root，那么root.left和root.right可选可不选，随意，由于f(root.left)和f(root.right)的结果只能为正，因此等于f(root.left) + f(root.right)。

如果采用分治递归，问题不大，但是要注意这种递归公式会出现大量相同子问题重复计算。所以要结合hashmap作memorization。

看基本情况，叶子node的解f(node) = node.val; 空节点的解f(null) = 0，因为没得偷。

方法二：g(root)表示一定选择root的最大解，h(root)表示一定不选择root的最大解。这次我们再考虑分治，有：

f(root) = max { g(root), h(root) };

g(root) = root.val + h(root.left) + h(root.right); 理解：选自己的解，一定要从左右子树中的一定不选择自己的最优解加起来；

h(root) = max { g(root.left), h(root.left) } + max { g(root.right), h(root.right) }; 理解：不选自己，不代表左右子树必须选自己，而是一种很自由的情况，左右子树选和不选自己都行， 但是注意我们需要分别在左右子树内部，选和不选这两种情况种选出较大的并加起来，这点比较难想到。

基本情况，对于叶子节点leaf, g(leaf) = leaf.val, h(leaf) = 0, g(null) = 0, h(null) = 0;

这种思路编码的时候，不再需要记忆化技巧，而是可以在每个结点计算两个值： 选择当前结点最优解，以及不选择当前结点可以得出的最优解。

这样，往父节点递归的时候，父节点可以轻松计算出自己的两个值。

PS. dp题目自下而上的编码，对于一维数组来说，就是从下标0开始计算，而对于二叉树来说，也就是从叶子节点开始往root计算。

174. Dungeon Game

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

解：首先想到此题是递归的。规定dp[i][j]表示从i，j处出发到达终点的最少初始血量，当然此题关键难考虑的点在于，英雄在血量低于0的时候直接gameover，所以， 在计算dp[i][j]的时候，一旦发现最小初始血量是0或负数的时候，其实要把它修正为1。理解：英雄虽然在后面的旅程中可以一帆风顺（吃大量血），但是在当前至少得活着有命才行。

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

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

自下而上，从右至左进行扫描。需要具有的最少血是右方、下方中最小值加上当前格子的消耗。消耗为负，就转为正加上去。

注意：终点处如果值为负数，那么初始血量减去消耗之后，一定要保证至少是1才行，也就是说如果是-5，那么要求初始血量为6，而不是5；如果值是正的，那么初始血量为1即可。

152. Maximum Product Subarray

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

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

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

674. Longest Continuous Increasing Subsequence

题意：寻找最长增长的substring。gs

解：此题使用动态规划。每次发现比前面一个数大的时候，局部最大从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减去最后一个元素的子问题，且是这些子问题答案的总和。

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

初始条件：dp[0] = 1。

理解：爬梯子里面是从前一步过来或者从前前一步过来，对应此题就是，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

题意：此题是求找零钱硬币组合数，与322的关系，322是求组合里大小最小的那个。

和377题(组合四)唯一区别是：[1,1,2]和[2,1,1]算重复。

解：本质是完全背包。完全背包就是物品选择方式次数不受限制。他与只能选一次(01背包)的计算时候区别在于，对于一个物品i，考虑不是选或不选，而是不选或者选1次，选2次…

完全背包中，除了求解的target的维度以外，在加入新的维度：可选元素分别是以0开始并以i下标为结束的集合，相当于每次比之前多考虑一个新加入的元素。

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

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

编码的时候，由于可选的物品数量没有target大，所以习惯性的把物品集合作第一个维度，把target作第二个维度。dp[i][j]表示i，j情况下的最少硬币组合。

dp[i][j] = dp[i - 1][j] + all { dp[i - 1][j - k*coins[i]] }。理解：每次新加入一个coin[i]的时候，都有选和不选两种情况：

要么是不选第i个物品，直接继承之前的结果（正上边的一个格子）；

要么选第i个物品，由于可以重复选，其实有k种选择，只要满足j - k * coins[i] >= 0且k > 0（如果等于0，那就是不选）。(完全背包依赖左上方若干格子，01背包是只依赖一个左上方格子)

初始条件: dp[0][0] = 1，理解：在集合为空的且target = 0的时候，默认为找到了一种组合数。同理，dp[i][0] = 1。

递推公式可以优化，考虑其中的all { dp[i - 1][j - k * coins[i]] }，实际上dp[i][j - coins[i]]和all { dp[i - 1][j - k * coins[i]] }是相等的,理解： dp[i][j - coins[i]] = dp[i - 1][j - coins[i]] + all { dp[i - 1][j - m * coins[i]] }，m就比k小1。

这样优化之后，它就只依赖正上方的一个格子和正左侧的一个格子。

PS.

1. 解和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做外重循环，表示一次只考虑一种硬币。

2.背包完全与01背包比较：01背包不可重复选的时候，依赖的是不选和之前一层只选一次过来的，也就是依赖正上方一个格子和左上方一个格子。

1. 硬币的面值需要是独特的，不能重复，否则计算的结果是不对的。

2. 如果是优化二维空间到一维，那么循环要变反为n从大到小循环。

221. Maximal Square

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

解：这种二维矩阵面积类型的问题，首先就要想到二维累加和的两个技巧： （0，0）（0，1）（0，2）… （1，0）（1，1）（1，2）… （2，0）（2，1）（2，2）… （3，1）（i, j）（i，y）… … … (x, j) (x,y) …

技巧一：求出（0，0）到（i，j）的面积（或者累加和）

使用动态规划，对于dp(i, j)，我们先计算dp(i - 1, j - 1), dp(i - 1, j)和dp(i, j - 1)。 考虑dp(i - 1, j) + dp(i, j - 1)，从面积上看，他们在减去其中的重叠部分，然后再加上(i - 1, j - 1)到(i, j)的部分就等于dp(i, j)。其中(i - 1, j - 1)到(i, j)的部分其实也就是 matrix[i][j]。总结得出公式: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]; 基本情况是：dp[0][0] = matrix[0][0]。

技巧二：求出(i, j)到 (x, y)的面积

公式就是：f[i ~ x][j ~ y] = dp[x][y] - dp[x][j] - dp[i][y] + dp[i][j]。理解：减去两部分，然后把多减去的重叠部分加进来。

结合这两种方法，可以暴力求解每个（i,j）开头的所有可能正方形，看面积是否等于累加和，如果等于，那么就找到一个实心1正方形，时间复杂度O(N^3)。

而此题使用特殊技巧。 思路是：dp[i][j]代表以坐标(i,j)必以右下角结尾的最大实心1正方形的边长大小：

dp[i][j] = 0， 如果matrix[i][j]==0，

如果matrix[i][j]==1，那么看dp[i-1][j-1], dp[i-1][j]和dp[i][j-1]三个中最小的+1。这点几乎很难想到。理解：这一步只是尝试在上一步的基础上加1， 重点参考dp[i - 1][j - 1]，如果它比dp[i-1][j]或dp[i][j-1]大，那么说明要在dp[i - 1][j - 1]基础上加1是不行了，但是可以在最短板处补上1，因为最短处往i，j处必然是全1。 如果dp[i - 1][j - 1]比两者都小，那它就是短板，因为它的外侧必然覆盖满了1。

二维矩阵动态规划题的一个通用思路，那就是考虑临近结点（不止一个，多数情况下是三个）作为子问题被解决后对当前格子的贡献。

编码：基本情况是第一行，第一列先计算出来。

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

673. Number of Longest Increasing Subsequence

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

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

解决方法是，在计算当前节点结尾的最长序列时候，考虑一个新的信息，也就是它作为结尾最长序列的时候，从之前哪个节点过来，那个节点的作为它最长序列的路径有多少条，

这样当前节点就能知道它的最长序列的路径多少条了，也就是倒数第二步的那些路径加起来。难度在于，当前节点连自己的最长序列长度都不知道是多少的时候，在扫描一遍的 时候，如何知道哪个节点就是自己的上一步节点？ 技巧在于，每次发现一个可以接过来的点的时候（比自己小的点），那么就看这个点加1和比当前的结果比较：

如果大，那么说明发现新路径了，那么之前记录的路径和不要了，立即更新路径和； 如果相等，说明目前的最长路径，数量需要更新了，也就是更新路径数； 如果较小，那么说明没有贡献。

注意：

1. 最终的结果，有可能不在一个节点上，例如最长路径是4，例如序列为1，2，3，9，8，7。其中的9，8，7都是最长路径为4，且它们之间是不同路径，因此要累加起来作为最后结果。
2. 注意[2,2,2,2]这种特例，要求是每个节点如果不能和之前节点有所链接，那么需要把当前路径长度和路径数都默认为1。

764. Largest Plus Sign

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

解：此题解法是对于每个位置，如果是1，那么查看以该位置为十字中心能够延展到多大的十字，一开始比较迷茫，应该它打破了二维数据dp的常用技巧：以某某坐标为结束的子问题。

因此需要打破常规，让求解的问题变形，回到熟悉的模式，也就是把复杂问题分解为若干简单的问题。

具体来说，此题既然十字形不好处理，那么干脆把十字形看作是四个线段的拼接，这样发现问题居然转化为以某节点为中心向左、向右、向上、向下延展的连续1中最短的那个。

接下来，就考虑如何求解向一个方向上的连续1？如果一个位置，它是0，那么结果也就是0；否则，虽然难考虑，但是我们仍然使用常见技巧，就是依赖它前一个位置的结果，也就是前一个位置结果+1。

所以可以使用动态规划求解。

编码：在自左向右，自上而下的方向的一遍扫描过程种，其实可以同时把向右和向下的结果求出来；同理，反向扫描得出向左和向上的结果。

最后，在进行一次扫描，这次考虑以元素为中心，四个方向哪个最小，那就是多大的十字形。 时间复杂度降为O(n^2)。

PS. 建立四个二维数组保存连续1的信息(4 * n^2)的空间复杂度。空间复杂度可以减少到1个n^2。 关心四个方向中最小的那个，也就是说，使用一个n^2的空间保留最终的结果，四个方向扫描过程中，只需要使用4个临时变量，然后如果该变量比最终结果小就更新（结果数组初始化为n）。扫描过程需要分开计算，不能两个双重循环得出答案，而是需要4个双重循环计算出四个方向的答案。

416. Partition Equal Subset Sum

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

解：此题是01背包问题，因为原问题可以转化为能否挑选出元素，和等于数组总和的一半。

01背包问题的解法套路就是:对于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。

初始条件：target = 0的时候，不管数组是什么，全是true；数组为空的时候，除了target = 0的以外，全是false。

还可以使用滚动数组来减少空间使用，因为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)表示加负号的集合的和（取正）。所以存在上面两步的转化。结果就是将原来的问题转化为416类似问题。本质就是01背包。 解法参考416。

注意边界条件： target + sum(nums)为奇数或负数的话结果直接返回0，sum < target时候也返回0。

309. Best Time to Buy and Sell Stock with Cooldown

题意：对一个数组，数组元素表示当天股票价值，现在求最大利润，只不过：

（1）当天只能买或卖,而且只能先买入后卖出，不能一直卖。

（2）卖股票之后，至少要等一天才能买

注意：再次买前必须卖，意思就是买卖是交替的，不能连买两次。

解：一开始以为此题意思是有本金M，每次买卖必是全买全卖，（最后一次卖掉获得的钱 - 本金）除以本金的百分比，也就是利润。

但是通过例子: prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell] 我们知道：如果初始本金100，在第一天买了100股，第二天卖掉，得到本金200，在第四天（价格0？？）买入，第五天卖，那不知道翻了多少倍了。。 所以此题其实要求的是在每天只买入一股或卖出一股的最大收益。

仍采用动态规划。与一般动态规划不同，此题需要考虑多种状态结尾，仔细分析，每天分为三个状态:hold,sold,rest。

hold[i]表示在第i天必须持有股票时的最大收益； sold[i]表示在第i天当天操作卖出股票且不持有股票的最大收益； rest[i]表示在第i天不操作且没有股票，它可以是cooldown，也就是由于之前一天卖出股票，今天不能买，没有股票的状态， 或者是之前的某天卖出了股票，今天不操作且没有股票；

得到三个方程： (1) hold[i] = max(rest[i-1] - prices[i], hold[i-1]) // 昨天(第i-1天)已经持有股票，那直接过来；昨天没持有股票，那必须是昨天没有操作的过来，今天买变成持有状态 (2) sold[i] = hold[i-1] + prices[i] // 今天必须卖，那么前提是昨天必须持有 (3) rest[i] = max(sold[i-1], rest[i-1]) // 今天不操作且没有股票，那昨天也不能有股票，从rest或者sold两种没持有的情况过来

答案在最后一天，当然状态不可能是hold，是sold和rest中最大的那个。

现在考虑三种状态的初始情况。第一天hold[0]=-prices[0],sold[0]= INT_MIN,rest[0]=0,因为第一天要是hold必须通过买进，消耗了prices[0]；无法卖出，所以初始化为负利润。

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

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

题意：此题与309不同之处在于，不需要冷冻，但是每次购卖的时候需要交交易费。题目要求在买之前必须卖，也就是说买卖股票一定是交替的，不能连买两次。

解：此题还是使用309的方法，这次的状态只有hold和sold。记住sold时候要考虑fee。

hold[i]的意思是在第i天持有股票的最大利润，sold[i]的意思是在第i天没有持有股票的最大利润。

hold[i] = max (hold[i - 1], sold[i - 1] - prices[i]); // 要么i-1天已经有股票了，今天不能买，直接等于昨天；要么i-1天没有股票，今天买使得处于有股票状态 sold[i] = max (sold[i - 1], hold[i - 1] + prices[i] - fee); // 要么第i-1天已经是没股票了，那么今天不能卖，直接等于昨天；要么昨天有股票，今天卖出使得处于没股票状态，并交费

初始情况： hold[0] = -prices[0]; // 第一天买股票，收益是负的。 sold[0] = 0; // 第一天没有股票，卖出去也是收益0。

结果是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]（理解：本质是完全背包，参考518题）。也可以是把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。

总结：

1. 此题最难的部分在于’*‘的考虑，一开始以为’*‘只是匹配任何s串的最后一个字符或多个字符，其实不然：’*‘一定要结合之前的一个字符来考虑，分两种大情况： 一种是之前一个字符x和s串（当前）最后一个字符可以匹配（例如相等或者之前的字符是’.’），这种又可以分为三种小情况来看，a) ‘*‘当作出现一次，也就是’x’ == ‘x’， b) ‘*‘当作出现多次，也就是’x’ == ‘xxx…‘， c) ‘*‘当作出现0次， ‘x’ = ‘‘； 一种是如果不匹配，那么把’x‘当作空来看，也就是出现0次的情况。

2. 编码难点在于初始情况难想，由于公式中，j依赖于j-2，所以j列的初始化不能仅仅初始化一列，而是要初始化两列，而继续分析，发现j依赖j-2的情况仅仅发生在p[j] == ‘*‘的时候， 而出现’*‘的时候，那至少之前是有两列，所以不需要初始化两列了。。。但是要注意第一行的初始化，例如s{}能匹配p{a,*}这种情况， 具体来说，还是动归思路，当元素为’*‘的时候， 只考虑’*‘当作空来看，也就是dp[0][j] = dp[0][j - 2]。

3. 一个违反直觉的地方：s串并不比p串长，相反，由于’*‘当作出现0次，p串可以比s串长。在二维的dp的时候，习惯性的把短的作纵坐标（数组第一维度）。

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]（理解参考518完全背包）。

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就是满足这种条件。

解：使用动态规划思路，假设dp[i]为最大子集必须以下标i结尾，那么答案一定在某个具体的i上。先从小到大排序，因为这样才能快速考虑比一个元素自己小的所有元素：大余小才有意义。

另外，我们观察1，2，4，8的规律，规律就是，只需要最后一个较小数余为0就可以了，因为4一定包含之前等比的情况，也就是一定比是2的情况。

剩下的一个问题是不仅要知道长度，也要知道具体数字。

解决方法就是，维持一个prev数组，记录最大值是从之前哪个元素更新而来（prev的值随着每次最大值进行更新）。

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，相当于是计算子集的题目：对于数组中一个元素，有选和不选两种情况，这样只要dfs回溯的搜索一遍，就可以得出答案。

一种是dp，就是从物品集合中01的选出若干物品，来满足一定的要求。由于此题不要求计算具体路径，所以使用dp。

此题独特之处，就是一种三维的dp，第一维以下标k结尾的集合，第二维m，第三维n。dp[k][i][j] 表示k,i,j三个维度消耗的最多子串。每次考虑新加入一个可选项k来考虑进一步规模的问题， 考虑选择第k项，以及不选第k项，不选第k项就是等价于dp[k - 1][i][j]，选择第k项，那么就是等价于dp[k - 1][i - k包含的0][j - k包含的1] + 1，加1的原因是此处多了一种匹配，也就是 当前第k项的匹配，考虑第k项的最终结果是二者（选或不选）中的较大者。注意一个细节，如果i - k包含的0或者j - k包含的1不合法，那么dp[k][i][j]要等于dp[k - 1][i][j]， 而不是0。

可以使用滚动数组在空间上进行优化（从N^3到N^2）。原理是k,i,j只依赖于k-1层和k层的结果，只需要记录二维的i，j信息即可，不过要注意依赖的是之前层的较小下标，因此循环的时候，下标要 从大到小计算，这样才不会破坏依赖的较小下标。

总结：如果不求具体路径，使用dp的是最好的，因为自底向上可以避免大量的重复计算。

808. Soup Servings

题意：给出初始值对(NA, NB)，有给出的四种方式s1(4, 0), s2(3, 1), s3(2, 2), s4(1 ,3)等概率来消耗原始值，现在求NA先消耗掉的概率。

解：此题是动态规划，因为递归情况存在大量重复。dp[i][j]代表i，j时候i先消耗掉的概率，那么等于0.25 * dp[i - 4][j] + 0.25 * dp[i - 3][j - 1] + 0.25 * dp[i - 2][j - 2]

• dp[i - 1][j - 3]。

再考虑基本情况：dp[0][0] = 0.5。因为同时消耗到0的概率是50%。dp[0][j] = 1 (j > 0的情况下) i < 0, j < 0的情况，同时小于0的情况等价于同时等于0，也就是50%，等价于i，j同时为0； i > 0, j < 0 的情况，概率是0，等价于i > 0, j = 0的情况。

此题要根据25做等比例修改，一个公式是(N - 1) / 25 + 1 或 (N + 24) / 25。

此题还有个最坑的点就是N很大的时候，内存却有限制。所以网上的解都是在N大于一定数的时候，数学上分析大概率99.99%是A先消耗完，直接返回1了。。

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]), i <= x <= j。此处使用min是由于动态规划，我们始终先知道子问题的解，所以可以有能力的选择到其中的花费最小的那个。

这正是动态规划的精髓：可以快速在很大解空间复杂路径中找到最优的解。

初始条件：i == j的时候，dp[i][j] = 0；因为猜对了是不支付的！

i > j的时候（公式里面的max (dp[i][x - 1], dp[x + 1][j])很容易出现这种情况），公式里面的该项就当作不存在（当0处理）。

PS. 使用记忆化搜索就可以计算出结果。

813. Largest Sum of Averages

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

解：此题是动态规划，考虑其中的子问题，一种是(i, j)数组分成x份，这就是三维动态规划dp[i][j][k]；或者是(0, i)数组分成x份。

此题只需要二维dp[i][x]就可以，因为如果分为三维，那么会出现重复考虑，例如前面一段分一段，后面一段分两段实际上和前面一段分两段后面一段分一段是等价的情况。

所以，dp[i][x]表示0到下标i切成x段的最大平均和，其中要求i要小于等于x，否则就是切分不了x份，当作边界情况0。

基本情况，dp[i][1]的意思就是切成一份，也就是数组和。dp[i][2]的意思是，以0到i为分界点划分成两份的结果。

dp[i][k]与dp[i][k - 1]的关系，也就是在0到i中在找一个分界点j，把0-j的部分看成是dp[j][k - 1]，剩余的部分看作是一份。 也就是dp[i][k] = max { dp[x][k - 1] + sum(x, i) / i - x}, 0 < x < i。

继续看基本情况：dp[0][0] = 0，dp[0][1] = nums[0]，dp[0][i] = sum(0, i) / i。

计算顺序，k紧紧依赖前一列，i依赖前面几行。因此，在循环的时候，一定遵照小下标先计算，也就是从小到大循环。

时间复杂度O(N^3)。

294. Flip Game II

题意：两个人每人一步翻转连续的++为–，直到对手没得选，自己就赢了。

解：此题一开始总觉得在自己可选的几个选项中也许有最佳的选择，然后考虑对手选择之后的在选。

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

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

PS. 和下棋一样，如果说棋局落入下风了，实际上的意思是，已经看到先手的失败了。

562. Longest Line of Consecutive One in Matrix

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

解：使用三维动态规划，dp[i][j][4]表示，下标i，j为结尾的最长的连续的1。每个格子只依赖前面的格子，如果为1，那么加1，否则是0。

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

361. Bomb Enemy

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

解：此题就是暴力求解，

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

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求出公共子序列长度，在将两串总长度减去该值,在乘以2得出答案。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]，例如定义dp[i][j]表示从区间[i, j]里玩游戏时候，先手能取出来的数字总和，这样只要dp[i][j]最终大于总和的一半，那么就算获胜。

自己在一开始两种中做出选择之后，变成了对方先手， 所以依赖的dp[i - 1][j]和dp[i][j - 1]是对手先手得出的结果。因此根据直觉，公式是：

dp[i][j] = max {dp[i + 1][j] + nums[i], dp[i][j - 1] + nums[j]}

但是这个直觉公式是不对的。

原因是对手先手时候，对手选的数自己是选不到的，且对手肯定会给自己留下较小的先手。因此在往下多看一层，得到公式：

dp[i][j] = max { min（ dp[i + 2][j]，dp[i + 1][j - 1] ) + nums[i], min (dp[i + 1][j - 1], dp[i][j - 2]) + nums[j] }

基本情况：i == j时候，dp[i][j] = nums[i]。i > j的时候，dp[i][j] = 0。

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

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

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

312. Burst Balloons

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

解：定义dp[i][j]为区间[i, j]问题的答案。

正方向想的话，就是打爆一个气球k后得到nums[k - 1] * nums[k] * nums[k + 1]，看剩余的子问题，也就是dp[i][k - 1]和dp[k + 1][j]。其中k的范围是i到j。 看起来似乎没有问题，但是实际上这个是错误的：考虑dp[i][k - 1]，如果其中选了k-1进行打爆，那么发现k-1的右侧邻居并不是nums[k]，因为k已经被打爆了，所以它的右侧邻居应该是dp[k + 1][j] 中的k+1。这就是说，公式中的nums[k - 1] * nums[k] * nums[k + 1]是不对的。

此题需要反方向想。反方向就是看n个气球中最后打爆哪个，有什么区别呢？k是最后一个被打爆的，意味着它正要被打爆的时候，i到k - 1和k + 1到j的气球已经被打爆了。 那么k的计算是固定的，就是nums[i - 1] * nums[k] * nums[j + 1] !!! 其中违反直觉的就是nums[i - 1]和nums[j + 1]，他们不一定是1的！

也就是有：dp[i][j] = max {dp[i][k - 1] + nums[i - 1] * nums[i] * nums[i + 1] + dp[k + 1][j]}

答案一定在某个被最后打爆的情况中。 编码知道，其中应该是三重循环，因此时间复杂度：O(n^3)。

但是三重循环的编码，下标很难考虑，因此，最好使用dfs+memo。

727. Minimum Window Subsequence

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

解：暴力解法思路就是：对于每一个和T串开头相同的字符开始到结尾，找最小包含的substring，使用经典双指针法，每次花费O(len(S) + len(T))的时间； 然后取出最短的一个作为答案，但是时间复杂度总的来说还是O(len(S) * (len(S) + 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]，问题退化成前一步的结果。

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变长的所有情况中，选择长度的最小的作为最终的答案。

dp的时间复杂度是O(len(S) * len(T))。

方法三：使用特殊的数据结构，next[i][k]，表示下标i的右手边离的最近的字母k的下标。构建这个数据结构也是dp思路： next[i][k] = next[i + 1][k], if S[i + 1] != k； // 意思是如果i+1处的字符如果不等于k，那么其实i处距离k字符结果完全可以继承i+1处； next[i][k] = i + 1, if S[i + 1] == k。 这样只需要双重循环，i从大到小，26次循环，计算出该数据结构。next[i][k]初始化为-1，表示右侧找不到字符k。

这样，对S串扫描，一旦开头等于T[0]，那么用这个数据结构进行快速计算最短substring，花费O(lenS * lenT)时间。

还可以使用改进的双指针解法，类似于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的距离。青蛙只能向前跳，且第一步青蛙只能跳一步，

也就是说，一开始默认之前是通过0跳过来的。

解：首先可以举出一些例子分析，发现路径是可能有多条的，且复杂。因此采取动态规划思路。

此题特殊之处在于每一步还是根据前一步的状态来看，所以难在想到应该加上之前走一步距离这个维度。

总之，我们定义dp[i][j]表示在下标为i的石头上，之前一步跳是j的情况，也就是说只要计算到了dp[i][j]，那么它一定是true。来看下一步：

计算i之后的下标x，如果x到i的距离是[j - 1, j, j + 1]其中一个，那么得到dp[x][y]，y代表j-1，j或者j+1其中一种具体情况。

初始情况，就是dp[0][0] = true，表示在第一块石头上，之前通过0的步骤过来。

在整理一下思路，发现关键是记录这种i和j，而且这种j不是连续的，也就是说，不是使用dp数组，我们使用hash表来记录是否出现了这种组合。 其中的j不止一个，可能是若干个。

二维hashmap的技巧就是：一个hashmap里面的值是另一个hashmap。最终的结果是，如果在最后一步，发现出现j至少一个，那就说明能到达。

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和j不能相连，那么问题规模缩小，说白了，缩减为考虑dp[i-1][j]和dp[i][j-1]中的较大者就好了。

再看基本情况：对于i和j同时为0时候，那么解看当前字母是不是相同，相同则是1，否则是0。在看dp[0][j]，也是看A[0]和B[j]是否相等，如果等则为1，否则递归为dp[0][j - 1]。

在仔细想想，发现，此题和求最长公共字序列是同样的问题：因为线之间不能交叉，和子序列相同是一个意思。

279. Perfect Squares

题意：求出加起来组成正数n，所用的最少的平方和数量，所谓平方和，就是指1，2，4，…。

解：此题是动态规划，要求n，递归到求比n规模小的子问题。对于n来说，它的规模更小的问题是n - i*i，只要保证n - i*i >= 0。 采用自底向上思路就是从1向n计算。

• Previous
  Leetcode按题目类型总结（十二）
• Next
  Leetcode按题目类型总结（十四）