注意：子数组是指连续序列
思想：
1.定义dp[i][j]为 以下标i为结尾的A，和以下标j为结尾的B，最长重复子数组长度为dp[i][j]
2.确定递推公式：当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
3.初始化：这里的初始化有些特殊，是nums[0]==nums[j]时候dp[0][j]=1，其余情况为0。dp[i][0]同理。
public int findLength(int[] nums1, int[] nums2) {
int[][] dp=new int[nums1.length][nums2.length];
if(nums1[0]==nums2[0])dp[0][0]=1;
else dp[0][0]=0;
//两个for循环初始化
for(int j=1; j
这里我的dp数组是以i、j结尾的子序列，其实这样会导致初始化有些复杂。
dp数组应该定义为下标i-1为结尾的A，和以下标j-2为结尾的B，最长重复子数组长度为dp[i][j]
这样初始化第一行和第一列就都是0，就不需要专门去初始化了，并且在找最大的res时候，只需要在填充dp的时候进行比较，而不需要专门去循环dp数组找出最大的数，如下所示：
public int findLength(int[] nums1, int[] nums2) {
int[][] dp=new int[nums1.length+1][nums2.length+1];
int res=0;
for(int i=1; i<=nums1.length; i++)
for(int j=1; j<=nums2.length; j++) {
if(nums1[i-1]==nums2[j-1])dp[i][j]=dp[i-1][j-1]+1;
res=Math.max(res, dp[i][j]);
}
return res;
}
可以看到代码简洁很多，并且复杂度减小了。
最长公共子序列 && 不相交的线
思想：
1.dp[i][j]： 长度为[0， i - 1]的字符串text1与长度为[0， j - 1]的字符串text2的最长公共子序列为dp[i][j]
2.状态方程：
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0， i - 2]与text2[0， j - 1]的最长公共子序列 和 text1[0， i - 1]与text2[0， j - 2]的最长公共子序列，取最大的。
即：dp[i][j] = max（dp[i - 1][j]， dp[i][j - 1]）;（这是连续和不连续子序列最大的区别
3.初始化：text1[0， i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
同理dp[0][j]也是0。
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp=new int[text1.length()+1][text2.length()+1];
for(int i=1; i<=text1.length(); i++)
for(int j=1; j<=text2.length(); j++) {
if(text1.charAt(i-1)==text2.charAt(j-1))dp[i][j]=dp[i-1][j-1]+1;
else {
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[text1.length()][text2.length()];
}
最长递增子序列
思想：
1.确定dp：dp[i]表示以nums[i]结尾的最长递增子序列
2.状态方程：
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if （nums[i] > nums[j]） dp[i] = max（dp[i]， dp[j] + 1）;
3.初始化：每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是1（数字本身）
public int lengthOfLIS(int[] nums) {
int[] dp=new int[nums.length];
Arrays.fill(dp, 1);
for(int i=1; inums[j])dp[i]=Math.max(dp[j]+1, dp[i]);
}
}
Arrays.sort(dp);
return dp[nums.length-1];
}
最长连续递增子序列
思想：相比上一道多一个连续的条件
1.dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
2.状态方程：
如果 nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度 一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。
即：dp[i + 1] = dp[i] + 1;
3.初始化：最小的长度就是数字本事，为1
public int findLengthOfLCIS(int[] nums) {
int[] dp=new int[nums.length];
Arrays.fill(dp, 1);
for(int i=1; inums[i-1])dp[i]=dp[i-1]+1;
}
Arrays.sort(dp);
return dp[nums.length-1];
}
最大子序和
思想：为连续的最大子序列和，无非就是两种情况前面的连续序列加上nums[i]，单独一个nums[i]
1. 确定dp：以nums[i]结尾的子序列的最大和为dp[i]
2.状态方程：dp[i-1]<0: dp[i]=nums[i]
dp[i-1]>=0: dp[i]=dp[i-1]+nums[i]
3.初始化
判断子序列
思想：这个和最长子序列一样，只需要判断最后的最长的长度是否等于较小序列s的长度即可
public boolean isSubsequence(String s, String t) {
int[][] dp=new int[s.length()+1][t.length()+1];
for(int i=1; i<=s.length(); i++)
for(int j=1; j<=t.length(); j++) {
if(s.charAt(i-1)==t.charAt(j-1))dp[i][j]=dp[i-1][j-1]+1;
else {
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[s.length()][t.length()]==s.length() ? true : false;
}
