【动态规划】1143. 最长公共子序列

1143. 最长公共子序列

解题思路

• dp[i][j] 表示序列s1[0,i-1] 和s2[0,j-1]之间的公共长度
• 当前字符s1[i]和s2[j]相同的话 那么memo[i][j] = memo[i - 1][j - 1] + 1;
• 如果不同， memo[i][j] = Math.max(memo[i][j - 1],memo[i - 1][j]);

class Solution {
    int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j] 表示序列s1[0,i-1] 和s2[0,j-1]之间的公共长度
        memo = new int[text1.length() + 1][text2.length()+1];

        // base case
        // 第一行和第一列 全部初始化为0  因为没有公共序列

        int m = text1.length();
        int n = text2.length();

        return dp(text1,text2,m,n);
        
    }

    int dp(String text1,String text2,int m,int n){

        if(m < 0 || n < 0){
            return 0;
        }


        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
            if(text1.charAt(i - 1) ==  text2.charAt(j - 1)){
                        // 表示该公共字符一定在lcs中  将之前的值 + 1
                        memo[i][j] = memo[i - 1][j - 1] + 1;
            }else{

                        // 当前字符不在lcs中  选取最大的
                        memo[i][j] = Math.max(memo[i][j - 1],memo[i - 1][j]);
            }
        }
    }

       

        return memo[m][n];
    }
}