【CT】LeetCode手撕—1143. 最长公共子序列

题目

• 原题连接：1143. 最长公共子序列

1- 思路

模式识别：最长公共子序列——> 动规五部曲

2- 实现

⭐1143. 最长公共子序列——题解思路

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //1. 定义 dp 数组
        int[][] dp = new int[text1.length()+1][text2.length()+1];

        //2.递推公式
        // if(text2.charAt(j) == text1.charAt(i)){ dp[i][j] = dp[i-1][j-1]+1;}
        // else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

        //3. 初始化
        
        //4. 遍历顺序
        for(int i = 1;i<=text1.length();i++){
            for(int j = 1 ; j<=text2.length();j++){
                if(text2.charAt(j-1) == text1.charAt(i-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[text1.length()][text2.length()];
    }
}

3- ACM 实现

public class longestSub {

    public static int longestSubString(String text1,String text2){
        // 1. 定义 dp 数组
        int[][] dp = new int[text1.length()+1][text2.length()+1];

        // 2.递推公式
        // if(text2.charAt(j-1) == text1.charAt(i-1)){ dp[i][j] = dp[i-1][j-1]+1;}
        // else {dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);}

        //3.初始化

        //4. 遍历
        for(int i = 1 ; i <= text1.length();i++){
            for (int j = 1 ; j <= text2.length();j++){
                if(text2.charAt(j-1) == text1.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }

    public static void main(String[] args) {
        System.out.println("输入text1");
        Scanner sc = new Scanner(System.in);
        String text1 = sc.next();
        System.out.println("输入 text2");
        String text2 = sc.next();
        System.out.println("结果为"+longestSubString(text1,text2));
    }
}