【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));}
}

---