1 最长公共子序列 LCS（相对顺序一致）
用二维数组记录每次遍历的状态，数组最后一个值是最长公共子序列长度
动态归纳法(dp)必须使用到数组，每个元素都是记录上一个比对的结果值。每一行都等待比对的值，每一列是作为比对的值。
583. 两个字符串的删除操作(删除字符串中公共子序列，需要多少步骤) Delete Operation for Two Strings medium
法1. 动态归纳法，时间复杂度O(nm)，空间复杂度(nm)
使用LCS公式，二维数组
此提求解的是找到使得 word1 和 word2 相同所需的最小步数
法2. 动态归纳法，时间复杂度O(nm)，空间复杂度(n)
使用LCS公式，一维数组，每行遍历都独立创建一个临时一维数组*
// 二维数组
private int findSubSeq(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int [][]x = new int[len1+1][len2+1];
for(int i=1; i<len1+1; i++) {
for(int j=1;j<len2+1;j++) {
char s = word1.charAt(i-1);
char t = word2.charAt(j-1);
if(s == t) {
x[i][j] = x[i-1][j-1] + 1;
} else {
x[i][j] = max(x[i-1][j], x[i][j-1]);
}
}
}
return x[len1][len2];
}
// 一维数组
private int findSubSeqOneArray(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int []x = new int[len2+1];
for(int i=0; i<len1; i++) {
char s = word1.charAt(i);
int []y = x.clone();
for(int j=1;j<len2+1;j++) {
char t = word2.charAt(j-1);
if(s == t) {
x[j] = y[j-1] + 1;
} else {
x[j] = max(x[j], x[j-1]);
}
}
}
return x[len2];
}
712. 两个字符串的最小ASCII删除和 Minimum ASCII Delete Sum for Two Strings
public int minimumDeleteSum(String s1, String s2) {
return total(s1) + total(s2) - 2 * findSubSeq(s1, s2);
}
private int max(int a, int b) {return a > b ? a : b;}
// 把每次获取到的最小子序列字符转换成ascii数字，进行累加
// 得到的结果就是分值最大的最小子序列分值
private int findSubSeq(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int []x = new int[len2+1];
for(int i=0; i<len1; i++) {
char s = s1.charAt(i);
int []y = x.clone();
for(int j=1;j<len2+1;j++) {
char t = s2.charAt(j-1);
if(s == t) {
x[j] = y[j-1] + t;
} else {
x[j] = max(x[j], x[j-1]);
}
}
}
return x[len2];
}
2 最长公共子串 DP（绝对顺序一致）
用二维数组记录每次遍历的状态
可以有化成一维数组，因为不需要记录以前的状态
由于是相对顺序，只要出现过一次，后续都在前一个值上+1
718. 最长连续重复子数组(两个数组) Maximum Length of Repeated Subarray
medium
法1. 动态规划 矩阵 时间复杂度O(m*n) 时间复杂度O(m*n)
因为输入的是两个数组，因此要保存状态需要二维数组
数组，多一行, 一列，保存初始值
二维数组如果连续子串，在二维矩阵表示是自左上角向右下角有值
保存的值是，当前所在位置最长的重复子数个数
row是第一个数组，列是第二个数组
法2. 动态规划 矩阵 时间复杂度O(m*n) 时间复杂度O(n)
使用一位数组保存状态，特性是每次值匹配时会dp[i-1][j-1] + 1
那么我们一维数组保存的上一个数组连续重复的值，为了使用dp[j-1]+1，我们从后往前遍历
53. 最大子序和(存在负数) Maximum Subarray easy
法1. 动态归纳法，时间复杂度O(n)，空间复杂度O(n)
使用dp[]记录第n个数组下标出现的最大子序和
- 这里要理解，
dp[i]=nums[i] + (dp[i-1]<0?0:dp[i-1])dp[i-1]就是子集的最大值，只有子集>=0才能增大现集，否则直接用当前值- 用一个max记录
3 最长公共前缀
3.1 传入二维数组，处理逻辑，返回字符串
14. 最长公共前缀 Longest Common Prefix easy
竖向法：（当很短比对就能立即结束比对）从第一个字符串开始逐字符遍历，第 i 个字符，与所有剩下字符串的第 i 个做对比，全部相等，往存储增加入第 i 个字符，否则，返回存储的字符串
4 最长递增
3. 无重复字符的最长子串 Longest Substring Without Repeating Characters medium
法1. 动态归纳法，时间复杂度O(n^2)，空间复杂度O(n)
使用dp[]记录第n个数组下标出现连续最多未重复的次数
并且用一个变量保存上一个数组最后一次重复的字符下标
n+1数组可以直接和n数组值进行比较取最大值
法2. 滑动窗口，时间复杂度O(n)，空间复杂度O(m)
利用一个Set<>保存最新的连续不重复子串，使用2个计数器，一个是窗口头，一个是窗口尾
每次存在重复字符时，开始缩小窗口，直到不存在重复字符时，开始增大窗口
300. 最长上升子序列 Longest Increasing Subsequence medium
法1. 动态归纳法，时间复杂度O(n^2)，空间复杂度O(n)
相对连续
使用dp[]记录第n个数组下标出现的最长上升子序列
n+1数组每次从0~n都做一次比较（因为新增的值可能比第0个值小）
法2. 动态归纳法-2分查找法，时间复杂度O(n)，空间复杂度O(n)
相对连续(todo)
673. 最长上升子序列子集合个数 Number of Longest Increasing Subsequence medium
todo
5 最长/短值
209. 值相加等于目标值，长度最小的子数组 Minimum Size Subarray Sum medium
法1. 动态归纳法 O(n^2), O(1)，dp，2层遍历实现连续子集，由于是连续的，可以使用一个状态变量来记录前一次的结果，减少第三层循环
法2. 滑动窗口 O(n), O(1)，双指针，使用第一个指针从左往右扫描, 找到大于目标值, 再用第二个指针从左往右缩小区间, 直到区间小于目标值(对比最小子集进行替换)，再用第一个指针继续向右扫描，依次类推
524. 删除字符串中某些字符，包含字典中的字符最长的，存在相同长度返回序列最小的 Longest Word in Dictionary through Deleting
594. 最长和谐子序列（最大值和最小值差1） Longest Harmonious Subsequence
法1. 时间复杂度O(n)，空间复杂度O(n)
使用Map记录所有key对应出现的次数，然后使用 key和key+1来统计最大值
521. 最长特殊序列 Ⅰ Longest Uncommon Subsequence I
首先，字符串相等不行，然后选长的字符串，一定不会是短的子集
