题解 | JAVA DP#最长公共子序列(一)# [P0-T2]

空间: O(Max(m, n))， 时间: O(mn)

定义LCS(i, j)为s1.substring(0, i+1)和s2.substring(0, j+1)的最长公共序列。
对于每一对i, j，以下两种情况：

如果s1[i] = s2[j], LCS(i, j) = LCS(i-1, j-1) + 1
如果s1[i] != s2[j], LCS(i, j) = MAX(LCS(i-1,j), LCS(i, j-1))

代码：

// no space optimization - O(mn) space.
import java.util.*;

public class Solution {
  public int LCS (String s1, String s2) {
    // dp[0][j] = 0, i.e. s2 is "".
    // dp[i][0] = 0, i.e. s1 is ""
    int dp[][] = new int[s1.length()+1][s2.length()+1];
    
    for (int i = 1; i <= s1.length(); i++) {
      for (int j = 1; j <= s2.length(); j++) {
        // -1 since dp[][] is 0 padded
        if (s1.charAt(i-1) == s2.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[s1.length()][s2.length()];
  }
}

// space optimization -O(Max(m, n)) space
import java.util.*;

public class Solution {
    public int LCS (String s1, String s2) {
      int[] mem = new int[s2.length() + 1];
      for (int i = 0; i < s1.length(); i++) {
        int tmp = 0;
        for (int j = 1; j <= s2.length(); j++) {
          if (s1.charAt(i) == s2.charAt(j-1)) {
            int prevj_1 = tmp;  // here tmp = LCS(i-1, j-1)
            tmp = mem[j];  // save mem[j] for j+1 iteration
            // LCS(i, j) = LCS(i-1, j-1) + 1
            mem[j] = prevj_1 + 1;
          } else {
            tmp = mem[j];  // save mem[j] for j+1 iteration
            // LCS(i, j) = MAX(LCS(i-1,j), LCS(i, j-1))
            mem[j] = Math.max(mem[j], mem[j - 1]);
          }
        }
      }
      return mem[s2.length()];
    }
}