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

最长公共子序列(一)

https://www.nowcoder.com/practice/672ab5e541c64e4b9d11f66011059498

总结:
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]);


    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
06-05 15:27
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务