474、一和零
给定一个包含 L 二进制字符串的二维数组 strs，求零的个数不超过 m，且一的个数不超过 n 的最大字符串个数。
该问题为零一背包问题，即背包中最多有 m 个 0 和 n 个 1。
第一种解法可定义一个三维数组 dp[L+1][m+1][n+1]，dp[i][j][k] 表示前 i 个字符串中，零的个数不超过 j，且一的个数不超过 k 的最大字符串个数。设第 i 个字符串的零一个数分别为 zero, one，那么：
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one])
其中 max 函数对两种情况取最大值，前一种是不采用第 i 个字符串，后一种是采用第 i 个字符串。
优化解法：code
定义二维数组 dp[m+1][n+1]，因为在第一种解法中，对第 i 个字符串遍历 k 和 j 求解时，只会用到第 i-1 个求解结果中 小于等于 k 和 j 位置的值，所以从后向前遍历 k 和 j，便可以将三维数组换位二维数组。
343、整数拆分 code
给定整数n，将n拆分为m个整数(m>1,且不指定)，求m个整数的最大乘积。
求n的最大乘积与小于n的整数的最大乘积相关，因此该问题可通过动态规划求解。
定义数组 dp[n+1]，其中dp[i]表示 i拆分为大于1个整数后的最大乘积。
由于0和1不能拆分，因此dp[0] = dp[1] = 0.
对于整数i，设其拆出的一个数为j，则剩余的 i-j 可以继续拆(i-j继续拆的最大乘积前面已求得，即dp[i-j])，也可以不拆(即i-j)，因此有动态规划方程：
dp[i] = max(dp[i], j * (i-j), j * dp[i-j])
其中j需要从0到i-1遍历。
121、买卖股票的最佳时机 code
最多只买一次，卖一次，求最大收益。
记录到目前为止的最小价格。
122、买卖股票的最佳时机 ii
和上题的不同在于，可以买卖多次股票，但是上一支股票卖出后才能买下一支股票。
方法一：code1
记录到目前为止的最小价格，只要有利润，就将股票卖出，并将最小价格记录为当前价格。
方法二：code2
动态规划。设p[i]为第i天(从0开始)的价格。
变量dp0记录当天交易完成后不持有股票的最大收益，dp1记录当天完成交易后持有股票的最大收益。
初始状态：
第一天不持有股票的收益为0，持有股票的收益为-p[0]，即
dp0, dp1 = 0, -p[0]
dp0 的状态转移方程：
dp0可以从前一天不持有股票(即dp0)转移过来，也可以从前一天持有股票(即dp1)并在今天卖掉(利润加上今天的价格p[i])转移过来，即
dp0 = max(dp0, dp1+p[i])
dp1可以从前一天持有股票(即dp1)转移过来，也可以从前一天不持有股票(即dp0)并在今天买入(利润减去今天的价格p[i])转移过来，即
dp0 = max(dp1, dp0-p[i])
最终的最大利润为 dp0，因为从状态转移方程可以看出 dp0 > dp1。
714、买卖股票的最佳时机含手续费 code
和上题的不同在于，买卖一次股票需要交一定的手续费。
由于手续费的存在，难以采用上题第一种方法，因此采用动态规划法。
198、打家劫舍 code
相邻的房屋不能一块抢劫，否则会触发报警，求可抢劫的最大收益。
定义 dp0 表示不抢劫当前房屋的最大收益，dp1 代表抢劫当前房屋的最大收益。第 i 间房屋的财产为 nums[i]。
初始状态：
不抢劫第0间房屋的收益为0，抢劫第一件房屋的收益为nums[0]，因此：
dp0, dp1 = 0, nums[0]
状态转移方程：
截止到第 i 间房屋，不抢劫该房屋的最大收益可由抢劫第i-1间房屋的最大收益，或者不抢劫第 i-1 间房屋的最大收益转移过来；抢劫该房屋的最大收益，只能由不抢劫第i-1间房屋的最大收益加上当前房屋的财产数转移过来。
dp0, dp1 = max(dp0, dp1), dp[0] + nums[i]
最终的最大收益为 max(dp0, dp1)
213、打家劫舍 ii code
和上题不同之处在于，首尾的房屋是相连的，也不能一块抢劫。
由于首位房屋不能一块抢劫，因此或者不抢劫第一间，或者不抢劫最后一间，则转化成了两种上题的情况，再在这两种情况间取最大值。
718、最长重复子数组
给定两个数组，求最长的公共子数组(子数组是连续的)的长度。
方法一：code1
在两个数组分别遍历子数组的开始位置，再求取连续子数组长度。
结果超时，时间复杂度O(n^3)。
方法二：cod2
动态规划。dp[i][j]代表以A数组的第i个元素结尾的子数组，与以B数组的第j个元素结尾的子数组的最大公共子数组的长度。
状态转移方程：
当A[i]==B[j]时，dp[i][j]=dp[i-1][j-1]+1，否则无公共子数组，dp[i][j]=0。
改进：code3
由于dp[i][j]只与dp[i-1][j-1]有关，因此可以定义一维数组dp，注意遍历j时要从大到小，否则从小到大会改变j-1的值。另外注意A[i]!=B[j]时，需要将dp[j]赋值为0。
494、目标和
给定一个由非负整数组成的数组，每个元素被赋予正号或负号，求可以实现和为S的方法数。
方法一：code1
使用dfs搜索。结果超时。时间复杂度：O(2^n),空间复杂度O(n)
方法二：code2
设数组大小为N。由于题目说明所有数组的和不大于1000，因此定义数组 dp[N][2001]，dp[i][j]代表前i个元素可实现和为j的种类数。i从0开始，dp数组全部初始化为0.
初始化：
由于前0个元素可实现和为nums[i]和-nums[i]，因此
dp[0][nums[i]+1000] += 1
dp[0][-nums[i]+1000] += 1
加1000是因为j在数组中对应下标j+1000，例如-1000对应0。
状态转移方程：
前i个元素和为j可由前i-1个元素和为j-nums[i]和前i-1个元素和为j+nums[i]两种情况转移过来，
因此：
dp[i][j+1000] = dp[i-1][j-nums[i]+1000] + dp[i-1][j+nums[i]+1000]
或者前i-1个元素和为j可转移到前i个元素和为j-nums[i]和前i个元素和为j+nums[i]这两种情况：(在程序中最好加上 if dp[i-1][j+1000] > 0:，因为j-nums[i]+1000可能小于0，而python负索引时会从后往前寻找元素)
dp[i][j+nums[i]+1000] += dp[i-1][j+1000]
dp[i][j-nums[i]+1000] += dp[i-1][j+1000]
结果：dp[-1][S+1000]
时间复杂度：O(2001n),空间复杂度O(2001n)
空间复杂度优化：code3
由于dp[i][j]只与dp[i-1]相关，因此可用两个数组代替。注意无法使用一个数组实现，因为dp[i][j]需要访问dp[i-1]中小于j的元素，也需要访问大于j的元素，正序或者倒序访问数组都不行。
进一步优化：code4
使用固定的长度为2001是数组不太合理，因为很多测试实例的和可能比较小。
因此先求出数组的和sum，然后构造大小为2*sum+1的数组。
300、最长递增子序列 code
设数组大小为N，定义数组dp[N]，dp[i] 代表以nums[i]结尾的的最长递增子序列长度。
初始化：
dp数组所有元素赋值为1，因为每个元素自身为长为1的序列。
状态转移方程：
对于dp[i]，需要遍历 j < i，如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)。
结果：max(dp)。
方法二：code2
序列seq初始为[ nums[0] ]，seq[i]表示长度为i+1的子序列的末尾元素的最小值。遍历nums中每一个元素n，当n大于seq[-1]，将n添加到seq。否则二分查找seq中第一个大于等于n的值，替换为n。最终seq的长度即最长递增子序列的长度。
参考：1 2
5、最长回文子串
状态转移：若某子串首尾字符不相等，则肯定不是回文子串；若首尾字符相等，则在去掉首位字符的字符为回文子串的情况下，该子串为回文子串。
定义dp数组，dp[i][j]代表以i开始以j结束的子串是否为回文串。
可以按照字串长度从小到大计算：code
或者遍历开始和结束下标，由于dp[i][j]依赖于dp[i+1][j-1]，因此起始下标需要从大到小。code2
279、完全平方数
方法一：code1
动态规划。定义数组dp，dp[i]表示数字i最少由dp[i]个完全平方数组成。dp[0]=0.
状态转移方程：
dp[i] = min(dp[i], dp[i-squre]+1)，即设i的某个完全平方数为squre，则其余i-squre已求得最少由dp[i-squre]个完全平方数组成，+1即再加上squre。其中squre需要遍历小于i的所有平方数。
注意：
在遍历小于i的所有平方数时，若j从1开始逐渐增加，并将j的平方与i相比，会超时（可能因为平方运算较耗时）。因此首先在squres数组中预先保存所有小于n的平方数。
方法二：code2
广度优先搜索。第0层为节点(n,0)，元组第一个元素为节点的值，第二个元素为深度。
第1层考虑所有小于n的平方数，由此可以将深度增加1。逐层增加深度，当某层元素为0时，则当前层深度为最少平方数个数。
注意：需要一个set记录遍历过的值，因为之前遍历过的值的深度小于等于当前层，所以在当前层分解该值的深度肯定大于等于该值在更浅层分解的深度。
此外，注意用que=deque((n,0))会将队列初始化为两个元素。应该先que=deque()，然后que.append((n,0))，则que由元组构成。
120、三角形最小路径和
方法一：dfs
超时，存在重复计算。
方法二：dfs+dp
记录已经求得的结果，已求得时，直接返回。
方法三：dp
从下往上求，dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]。
每求完一行，pop掉最后一个元素。
1262、可被三整除的最大和 code 参考
定义大小为3的dp数组，dp[i]表示余数为i的最大和，dp初始各元素初始化为0。
遍历每一个元素n，对与dp[i]来说，dp[i]+n的余数会变成：new_mode=(dp[i]+n)%3，为求最大和，使dp[new_mode] = max(dp[new_mode], dp[i]+n)。
注意每次遍历一个元素n，计算新的dp数组时，需要用上一个dp数组的元素计算，因此代码中for m in dp[:]产生了旧dp数组的一个copy。
注意不要使new_mode=(i+n)%3，因为dp[i]的余数不一定是i（初始化为0），new_mode=(dp[i]+n)%3则不会有问题。
1035、不相交的线 code
题目要求连线的数字相等，各线段不相交，即各线段的两端点的下标在各自数组都是递增的，因此是最长公共子序列问题。
486、 预测赢家
方法一：递归 code1
当前的先手有两种选择，应该选择递归返回的结果加上选择的结果更大的那个。
方法二：动态规划
在递归时，先手或后手存在重复计算。因此用dp数组记录，dp[i][j][0]、dp[i][j][1]表示第i个到第j个元素，先手、后手分别获得的最大分数。则先手会选择dp[i][j-1][1]+nums[j]和dp[i+1][j][1]+nums[i]中较大的一种。
