题解 | #最长公共子序列(一)#

总结：
1.由于当截取字符串a从0到i,截取字符串b从0到j，此时两截取的字符串的最长公共子序列与前面的状态有关，并可写出状态转移方程，故使用动态规划可以解决。关键是想出状态转移方程。
dp[i][j]= dp[i−1][j−1]+1, 当text1​[i−1]=text2​[j−1]时
max(dp[i−1][j],dp[i][j−1]),当text1​[i−1]不等于text2​[j−1]​

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] num = sc.nextLine().split(" ");
        int m = Integer.parseInt(num[0]);
        int n = Integer.parseInt(num[1]);
        String text1 = sc.nextLine();
        String text2 = sc.nextLine();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(i==0||j==0)
                    dp[i][j]=0;
                else{
                    if(text1.charAt(i-1)==text2.charAt(j-1))//由于dp数组i=0j=0空闲，数组dp[i][j]就对应字符串的i-1,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]);
                }
            }
        }
        System.out.println(dp[m][n]);


    }
}