1143. 最长公共子序列 - Java 动态规划

原题地址：https://leetcode.cn/problems/longest-common-subsequence

题解

最长公共子序列是一道DP模板题，面对这类问题有相近的思路

开一个二维数组dp，dp[i][j]表示text1.substring(0,i)和text2.substring(0,j)的最长公共子序列

当我们遍历到dp[i][j]时，有两种情况

• text1.charAt(i)==text2.charAt(j)
  • 这种情况可以认为是两个字串XXX和XXX各往前扫描了一位，然后XXXA和XXXA正好可以匹配一位
  • 因此dp[i][j]=dp[i-1][j-1]
• text1.charAt(i)!=text2.charAt(j)
  • 这种情况XXXA和XXXB不能匹配，因此情况等同于A/B没有被扫描到的情况（就像打家劫舍里的小偷一样，如果不偷这间房子实际上约等于这间房子不存在/没有被遍历到）
  • 因此dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
  • 由于递归扫描的情况（在计算dp[i-1][j]和dp[i][j-1]的时候已经把dp[i-1][j-1]考虑在内了），因此dp[i-1][j-1]是可以省略掉的
  • 因此dp[i][j]=max(dp[i-1][j],dp[i][j-1])

时间复杂度：O(MN)

空间复杂度：O(MN)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp=new int[text1.length()+1][text2.length()+1];
        for(int r=1;r<dp.length;r++){
            for(int c=1;c<dp[r].length;c++){
                if(text1.charAt(r-1)==text2.charAt(c-1))
                    dp[r][c]=dp[r-1][c-1]+1;
                else
                    dp[r][c]=Math.max(dp[r][c-1],dp[r-1][c]);
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }
}