1. 最长递增子序列（注意不连续）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1）动态规划

dp[i]--------到i为止包括i递增子序列的长度，最后一位必须包括nums[i]

dp[i]=Math.max(dp[0],dp[1],....,dp[i-1])+1;

if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);

 public int lengthOfLIS(int[] nums) {if (nums.length==1) return 1;int[] dp=new int[nums.length];int result=1;for(int i=0;i<nums.length;i++) {dp[i]=1;}for(int i=1;i<nums.length;i++){//for(int j=0;j<i;j++){if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);}if(dp[i]>result) result=dp[i];}return result;}

2) 贪心

思路：上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小

维护数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，用len 记录目前最长上升子序列的长度，起始时 len为 1，d[1]=nums[0]。

注意：d[i] 是关于i单调递增的。

依次遍历数组 nums ，并更新数组 d 和 len的值。如果nums[i]>d[len] 则更新 len = len + 1，否则在 d[1...len]中找满足d[i−1]<nums[j]<d[i] 的下标 i，并更新d[i]=nums[j]。根据d数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

最后整个算法流程为：

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到nums[i] 时：

如果nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新len=len+1；

否则，在 d数组中二分查找，找到第一个比 nums[i] 小的数 d[k]，并更新 d[k+1]=nums[i]。

2. 重复子数组

解题套路：dp[i][j]------>以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最⻓重复⼦数组⻓度为dp[i][j]

2.1) 最⻓重复⼦数组

class Solution {
//dp[i][j]->以下标i-1为结尾的A,和以下标j-1为结尾的B,最⻓重复⼦数组⻓度为dp[i][j]public int findLength(int[] nums1, int[] nums2) {//想要得到dp[nums1.length][nums2.length]int[][] dp=new int[nums1.length+1][nums2.length+1];dp[0][0]=0; int result=0;for(int i=1;i<=nums1.length;i++){//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;if(dp[i][j]>result) result=dp[i][j];}}return result;}
}

2.2）最⻓公共⼦序列

class Solution {
/*dp[i][j]->⻓度为[0,i-1]的字符串text1与⻓度为[0,j-1]的字符串text2的最⻓公共⼦序列为dp[i][j]如果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]的最⻓公共⼦序列，取最⼤的。
*/
public int longestCommonSubsequence(String text1, String text2) {//想要得到dp[text1.length()][text2.length()]int[][] dp=new int[text1.length()+1][text2.length()+1];if(text1==null||text2==null||text1.length()<=0||text2.length()<=0) return text1.length()<=0? text2.length():text1.length();dp[0][0]=0; 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()];}
}

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp=new int[nums1.length+1][nums2.length+1];dp[0][0]=0; int result=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;else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);if(result<dp[i][j]) result=dp[i][j];}}return result;}
}

class Solution {/*dp[i][j]----以i-1为结尾的s⼦序列中出现以j-1为结尾的t的个数为dp[i][j]。s[i-1]=t[j-1]dp[i][j]=dp[i - 1][j - 1] + dp[i - 1][j];s[i-1]!=t[j-1] dp[i][j]=dp[i - 1][j]*/public int numDistinct(String s, String t) {int[][] dp=new int[s.length()+1][t.length()+1];for(int i=0;i<s.length();i++) dp[i][0]=1;for(int j=1;j<t.length();j++) dp[0][j]=0;for(int i=1;i<s.length()+1;i++){for(int j=1;j<t.length()+1;j++){if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];else dp[i][j]=dp[i-1][j];   }}return dp[s.length()][t.length()];}
}

class Solution {/*dp[i][j]-----s1在i-1，s2在j-1相同的最少步数*/public int minDistance(String word1, String word2) {int[][] dp=new int[word1.length()+1][word2.length()+1];for(int i=0;i<=word1.length();i++) dp[i][0]=i;for(int j=0;j<=word2.length();j++) dp[0][j]=j;for(int i=1;i<word1.length()+1;i++){for(int j=1;j<word2.length()+1;j++){ if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];else dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;}}return dp[word1.length()][word2.length()];}
}

2.7) 回⽂⼦串

   1)动态规划

class Solution {public int countSubstrings(String s) {if (s == null || s.length()< 1) return 0;int result=0;boolean[][] dp=new boolean[s.length()][s.length()];for(int i=s.length()-1;i>=0;i--){for(int j=i;j<s.length();j++){if(s.charAt(i)==s.charAt(j)&&((j-i<=2)||dp[i+1][j-1])){dp[i][j]=true;result++;}} } return result; }}

class Solution {public int countSubstrings(String s) {if (s == null || s.length()< 1) return 0;int result=0;for (int i = 0; i < s.length(); i++) {result += extend(s, i, i, s.length()); // 以i为中⼼result += extend(s, i, i + 1, s.length()); // 以i和i+1为中⼼}return result;}public int extend(String s, int i, int j, int length) {int res=0;while(i>=0&&j<length&&(s.charAt(i)==s.charAt(j))){i--;j++;res++;}return res;}}

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp=new int[s.length()][s.length()];for (int i = 0; i<s.length(); i++) dp[i][i] = 1;for(int i=s.length()-1;i>=0;i--){for(int j=i+1;j<s.length();j++){if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;else dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);}}return dp[0][s.length()-1];}
}