|
1.最大连续乘积子数组（数组中的元素有正数有负数）
解法一：暴力法
两个for循环确定边界，可以找出所有数组的乘积然后在进行比较。时间O（N的平方）
解法二：动态规划
设f（i）是以第i个元素结尾的最大连续子数组。由于有负数的存在，那么f（i-1）就需要维护一个最大值和一个最小值（为负数），只有这样才能求出f（i）的最大。时间O（N），空间也可以常量，因为每一次的计算只需要用到上一次的信息而不需要以前的历史信息。
引申扩展：
计算组合中乘积最大的一组。给定长度为n的数组，计算其中n-1个数乘积最大的一组。
解法一：直接暴力法，找出这n个组合，然后分别计算出乘积，时间O（N的平方）
解法二：画图然后使用先逆向求积，在正向求积。时间和空间都为O（N）。
逆向：1 ，1*An-1，1*An-1*An-2 ...... 1*An-1....A2 ；正向：b[1]*1，b[2]*1*A1，b[3]*1*A1*A2 ..... ，b[n]*1*A1*.....An-1；
ps：为了方便下标都从1开始。
2.编辑距离
给定一个字符串使用最少的修改次数来变为目标穿（有插入，替换，删除三种方式）
设dp（i，j）为字符串的前i个字符到目标串的前j个字符的最小代价。如果替换/修改操作dp（i，j）=dp（i-1，j-1）（是修改过可以匹配的！）+1，如果是插入操作dp（i，j）=dp（i，j-1）（是修改过可以匹配的！）+1，如果是删除操作dp（i，j）=dp（i-1，j）（是修改过可以匹配的！）+1。还有就是，是可以进行空间优化的！
ps：dp（i-1，j-1）代表把前i-1个字符编辑成j-1个字符的最小代价。然后把字符串a最后一个字符替换为b的最后一个字符。
ps：dp（i，j-1）代表把前i个字符编辑成j-1个字符的最小代价。然后在给字符串a添加最后一个字符j。
ps：dp（i-1，j）代表把前i-1个字符编辑成j个字符的最小代价。然后在给字符a删除最后一个字符i。
ps：初始化时，要注意位置0的含义，代表空字符串！要特别注意这个空串，因为跟其他动态规划在这点不一样。
3.格子取数
给定矩阵，元素非负，从左上角走到右下角，每次只能向右和向下走。
设dp（i，j）为走到位置（i，j）的最优路径。位置（i，j）只能有两种途径，dp（i，j）=min（dp（i-1，j），dp（i，j-1））+Wi,j即可。
引申扩展：
格子取数加强版，如果格子中有障碍呢？
直接把dp（i，j）的位置，置为无穷大，因为该位置不可到达必须置无穷大，让此位置不可选。
数塔取数问题，给一个三角形，元素只能到它的相邻元素去？
思路和格子取数差不多，但是要注意边界条件，需要额外判断额外处理。
4.交替字符串
给定s1，s2和s3三个字符串，判断s3是否可以由s1和s2交错组合而成。
首先不能排序因为会改变s1和s2的相对位置，考虑动态规划的思路，
设dp（i，j）代表s1串的前i个字符和s2串的前j个字符是否可以交错组成s3的前i+j个字符。if s3[i+j]==s1[i] 且 dp[i-1][j]==True 或者 s3[i+j]==s2[j] 且 dp[i][j-1]==True 则dp[i][j] = True。
ps：暴力递归法，也是选a还是选b的问题。
5.换钱最少的硬币数
每个面值可以使用多次，该问题与01问题不同，因为只能装一次，但是大致思路是一样的。
思路一：直接暴力递归，每次都有n-i种选择，最后返回花费最少数量的结果。
ps：由于有大量重复值计算，可以使用一个和dp一样规格的数组，来记录计算过的值。
设dp[i][j]代表前i个物品可以让目标j最少的货币数/价值最大。
思路二：if j-x*arr[i]>0 && dp[i][j-arr[i]]!=MAX 则dp[i][j]=min(dp[i-1][j-x*arr[i]]+x,dp[i-1][j]) ；x>=1 选不选此面值
01背包的思路：if j-arr[i]>0 则 dp[i][j] = max(dp[i-1][j],dp[i-1][j-arr[i]]+V[i]) 选不选此物品
注意：由于一个物品可以多选，背包问题不需要多选，递归方式的写法一个有循环一个没有循环。
思路三：dp（i）代表钱数为i时最少的货币数。dp（i）= min（dp（i-coins（j）））j：0--coins.sizes()。
ps：这思路也很好！
扩展：换钱的方法数，由于子问题需要累加，需要三个循环，外层的两个限制起始和结束边界，内层的是子问题。
ps：基于第三种思路，只需要两个循环即可，子问题叠加即可。
class Solution {
public:
int change(int n, vector<int>& coins) {
int m = coins.size();
vector<int> dp(n+1, 0);
dp[0] = 1;
for (auto c: coins) {
for (int i = c; i <= n; i++) {
dp[i] += dp[i - c];
}
}
return dp[n];
}
};
6.最长递增子序列
注意：子序列和子数组的区别，一个不连续一个连续。
思路一：申请一个dp（i）代表以i结尾的最长子序列长度，需要两个for循环因为不连续所以每次确定都要在i位置以前在判断还有没有可以连接成为最长的序列。
思路二：对子序列排序得到L2，然后求L1和L2的最长公共子序列。dp（i，j）第七题。
7.最长公共子序列
注意：子串和子序列的区别，一个连续一个不连续。
思路：设dp（i，j）为两个字符串在位置i和j的最长公共子序列，dp（i，j）在if s[i]!=s[j]时由dp[i-1][j]或dp[i][j-1]来决定，就是两个字符串需要谁移动一位，正是因为这样才会传递出来子序列。if s[i]==s[j]则为dp[i-1][j-1]+1。
扩展：最长公共子串，这个需要连续，所以dp（i，j）代表以s1[i]和s2[j]结尾的字符串的最长子序列。if s[i]!=s[j]时dp[i][j]应该置零，就是你不能在进行传递了；相等时应该加1！
8.数字字符串转换为字母组合的种数
str="11111"字母只能由1位或者两位来构成。
思路：类似斐波那契和跳台阶的问题f（n）=f（n-1）+f（n-2），但是条件受限两位数必须小于26一位数必须大于1。使用递归，在使用map存储优化，在使用自底向上dp优化，基矩阵的n次幂需要快速幂（使用了二进制的求和思路）。
9.表达式得到期望结果的组成种数
字符串：“0^1|0&1|0”在给一个期望结果express：true/false，求划分的方式有多少种。
思路：首先应该对表达式进行验证看是否正确（奇数位，偶数位，表达式长度）；使用暴力递归的方式，每个符号都可以划分为左表达式和右表达式，然后确定express的状态在进行递归下去。
ps：start-end中的符号都可以递归下去分割为两部分。
10.纸牌博弈问题
一个数组，只能从左或者右取值，两位玩家都绝顶聪明。返回最后获胜者的分数。
思路：有先拿和后拿的区别而且都是一个递归的过程，那么需要两个递归函数和一个主函数，f代表先拿因为绝顶聪明一定会递归的找到最大，然后变为后拿，s代表后拿因为是绝顶聪明那么先拿的一定会留下最小的值，然后变为先拿。main函数返回先拿和后拿的获胜者，时间复杂度为2的N次方。
11.数组中的最长连续序列
[100,2,200,1,4,3] == [1，2，3，4]，序列连续是每次只能差1。
思路一：可以使用排序，然后在遍历一遍，更新最长连续序列即可。
思路二：使用hash表，每个遍历过的字符都会存到hash表里，value值为连续序列的长度，每遍历到一个字符都判断小于和大于它的字符是否出现过，进行更新最长序列即可。
12.N皇后问题
思路：依次递归的放每个皇后，在这个过程会记录前面皇后放在的对应列，以及目前放成功的皇后数，每个递归都会穷举每个位置在这里要验证是否安全（不能在同行同列出现，不能在对角线出现）。
13.最长不含重复字符的子字符串
思路：设dp（i）代表以第i个字符结尾的最长不重复子串，需要使用一个哈希表来记录第i个字符是否在以前出现过，如果没出现过dp（i）=dp（i-1）+1，，如果出现过而且他们之间的长度为d且大于dp（i-1）那么dp（i）还是等于dp（i-1）+1，长度小于等于d的时候dp（i）就等于d。
14.股票的最大利润
给出一些时间点的价格，时间是有序排列。
思路一：使用暴力法，构造出所有的数对，找出最大的差异。
思路二：设dp（i）为在第i个时间段卖出的最大收益。需要记录前i时间段的最低价格，即可。
ps：双指针l和r，每一次r指向当前元素，l指向当前元素前的最小值！
15.矩阵中最大的正方形
思路：dp[i][j] := 以 M[i][j] 为正方形**右下角**所能找到的最大正方形的边长。注意返回的是最小的边长，是个与的过程。
在一个由 0 和 1 组成的二维矩阵 M 内，找到只包含 1 的最大正方形，并返回其面积。
递推公式：dp[i][j] = min{dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1]} + 1 若 M[i][j] == 1
= 0 否则
小结：动态规划可以先使用递归来实现，由于自上向下计算，会计算很多重复，也正是由于自上向下计算那么可以把先计算出来的小问题存储下来，防止重复计算降低复杂度；还可以直接使用dp实现自底向上的计算。
16. 给定数组{a1, a2, a3, ... an}，要求挑出一些数，这些数不能相邻，使得加起来的和最大。
思路：需要使用两个动态规划数组，一个是前i项最大的加和，一个是以第i项结尾的最大加和。 | 
转播
