674. 最长连续递增序列

  1. int[]dp=new int[nums.length];
  2. dp[0]=1;
  3. int res=1;
  4. if(nums.length==1){
  5.   return res;
  6. }
  7. for(int i=1;i<dp.length;i++){
  8.   if(nums[i]>nums[i-1]){
  9.     dp[i]=dp[i-1]+1;
  10.     res=Math.max(res,dp[i]);
  11.   }else{
  12.     dp[i]=1;
  13.   }
  14. }
  15. return res;

718. 最长重复子数组

  1. int[][]dp=new int[nums1.length+1][nums2.length+1];
  2. int res=0;
  3. for(int i=1;i<dp.length;i++){
  4.   for(int j=1;j<dp[0].length;j++){
  5.     if(nums1[i-1]==nums2[j-1]){
  6.       dp[i][j]=dp[i-1][j-1]+1;
  7.       res=Math.max(res,dp[i][j]);
  8.     }
  9.   }
  10. }
  11. return res;

1143. 最长公共子序列

  1. int[][]dp=new int[text1.length()+1][text2.length()+1];
  2. for(int i=1;i<dp.length;i++){
  3.   for(int j=1;j<dp[0].length;j++){
  4.     if(text1.charAt(i-1)==text2.charAt(j-1)){
  5.       dp[i][j]=dp[i-1][j-1]+1;
  6.     }else{
  7.       dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
  8.     }
  9.   }
  10. }
  11. return dp[dp.length-1][dp[0].length-1];

1035. 不相交的线

  1. int[][]dp=new int[nums1.length+1][nums2.length+1];
  2. for(int i=1;i<dp.length;i++){
  3.   for(int j=1;j<dp[0].length;j++){
  4.     if(nums1[i-1]==nums2[j-1]){
  5.       dp[i][j]=dp[i-1][j-1]+1;
  6.     }else{
  7.       dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
  8.     }
  9.   }
  10. }
  11. return dp[dp.length-1][dp[0].length-1];

392. 判断子序列

  1. if(s.length()>t.length()){
  2.   return false;
  3. }
  4. boolean[][]dp=new boolean[s.length()+1][t.length()+1];
  5. for(int i=0;i<dp[0].length;i++){
  6.   dp[0][i]=true;
  7. }
  8. for(int i=1;i<dp.length;i++){
  9.   for(int j=1;j<dp[0].length;j++){
  10.     if(s.charAt(i-1)==t.charAt(j-1)){
  11.       dp[i][j]=dp[i-1][j-1];
  12.     }else{
  13.       dp[i][j]=dp[i][j-1];
  14.     }
  15.   }
  16. }
  17. return dp[dp.length-1][dp[0].length-1];

115. 不同的子序列

  1. int[][]dp=new int[t.length()+1][s.length()+1];
  2. for(int i=0;i<dp[0].length;i++){
  3.   dp[0][i]=1;
  4. }
  5. for(int i=1;i<dp.length;i++){
  6.   for(int j=1;j<dp[0].length;j++){
  7.     if(t.charAt(i-1)==s.charAt(j-1)){
  8.       dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
  9.     }else{
  10.       dp[i][j]=dp[i][j-1];
  11.     }
  12.   }
  13. }
  14. return dp[dp.length-1][dp[0].length-1];

583. 两个字符串的删除操作*

  1. int[][]dp=new int[word2.length()+1][word1.length()+1];
  2. for(int i=1;i<dp[0].length;i++){
  3.   dp[0][i]=i;
  4. }
  5. for(int i=1;i<dp.length;i++){
  6.   dp[i][0]=i;
  7. }
  8. for(int i=1;i<dp.length;i++){
  9.   for(int j=1;j<dp[0].length;j++){
  10.     if(word2.charAt(i-1)==word1.charAt(j-1)){
  11.       dp[i][j]=dp[i-1][j-1];
  12.     }else{
  13.       dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
  14.     }
  15.   }
  16. }
  17. return dp[dp.length-1][dp[0].length-1];

72. 编辑距离*

  1. int[][]dp=new int[word2.length()+1][word1.length()+1];
  2. for(int i=0;i<dp.length;i++){
  3.   dp[i][0]=i;
  4. }
  5. for(int i=0;i<dp[0].length;i++){
  6.   dp[0][i]=i;
  7. }
  8. for(int i=1;i<dp.length;i++){
  9.   for(int j=1;j<dp[0].length;j++){
  10.     if(word2.charAt(i-1)==word1.charAt(j-1)){
  11.       dp[i][j]=dp[i-1][j-1];
  12.     }else{
  13.       dp[i][j]=Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
  14.     }
  15.   }
  16. }
  17. return dp[dp.length-1][dp[0].length-1];

647. 回文子串*

  1. int res=0;
  2. boolean[][]dp=new boolean[s.length()][s.length()];
  3. for(int j=0;j<dp.length;j++){
  4.   for(int i=0;i<=j;i++){
  5.     if(s.charAt(j)==s.charAt(i)&&(j-i<2||dp[i+1][j-1])){
  6.       dp[i][j]=true;
  7.       res++;
  8.     }
  9.   }
  10. }
  11. return res;

516. 最长回文子序列*

  1. int[][]dp=new int[s.length()][s.length()];
  2. for(int i=0;i<s.length();i++){
  3.   dp[i][i]=1;
  4. }
  5. int res=1;
  6. for(int i=s.length()-2;i>=0;i--){
  7.   for(int j=i+1;j<s.length();j++){
  8.     if(s.charAt(i)==s.charAt(j)){
  9.       dp[i][j]=dp[i+1][j-1]+2;
  10.       res=Math.max(dp[i][j],res);
  11.     }else{
  12.       dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
  13.     }
  14.   }
  15. }
  16. return res;