1.最长递增子序列(一维dp)

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

转移方程：dp[i] = Max(dp[i], 1 + dp[j])

base case : 子序列长度初始化为1

  1. public int lengthOfLIS(int[] nums) {
  2.     int[] dp = new int[nums.length];
  3.     // base case：dp 数组全都初始化为 1
  4.     Arrays.fill(dp, 1);
  5.     for (int i = 0; i < nums.length; i++) {
  6.         for (int j = 0; j < i; j++) {
  7.             if (nums[i] > nums[j]) 
  8.                 dp[i] = Math.max(dp[i], dp[j] + 1);
  9.         }
  10.     }
  12.     int res = 0;
  13.     for (int i = 0; i < dp.length; i++) {
  14.         res = Math.max(res, dp[i]);
  15.     }
  16.     return res;
  17. }

2.最长回文子序列(二维dp)

image.pngimage.png
image.pngˇ

转移方程：i，j从字符串两端向中间比较

if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

base case : i == j时，即字符串长度为1时，回文串长度也为1

public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for(int i = 0 ; i < n ; i++){
            dp[i][i] = 1;
        }

        for(int i = n - 2 ; i >=  0 ; i--){
            for(int j = i + 1; j < n ; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]);
                }
            }
        }

        return dp[0][n - 1];

    }

3.最长公共子序列(二维dp)

image.pngimage.png

转移方程：两个字符串从同一侧开始比较

if(text1.charAt(i) == text2.charAt(j)){
    dp[i][j] = 1 + dp[i + 1][j + 1];
}else{
    dp[i][j] = Math.max(
        dp[i + 1][j],
        dp[i][j + 1]
    );
}

public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for(int i = m - 1 ; i >= 0; i --){
            for(int j = n - 1 ; j >= 0 ; j--){
                if(text1.charAt(i) == text2.charAt(j)){
                    dp[i][j] = 1 + dp[i + 1][j + 1];
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j],
                    dp[i][j + 1]);
                }
            }
        }

        return dp[0][0];
    }