LeetCode1143.最长公共子序列

2023-12-14 22:48:35

?这道题看完就大概知道要用动态规划,然后想想如何建立动态转移方程,就很简单了,我都感觉我不是想出来的,是根据直觉应该是这样的然后边想边写就出来,以下是我的代码:

?

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        int n1 = c1.length;
        int n2 = c2.length;
        int[][] dp = new int[n2+1][n1+1];
        for(int i = 1;i<=n2;i++){
            for(int j = 1;j<=n1;j++){
               if(c1[j-1] == c2[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[n2][n1];
    }
}

状态定义:?

我们建立一个二维数组dp,dp[i][j]表示拿text2的前i个字母和text1的前j个字母最多有几个公共子串。

初始状态:

我们建立一个大小为[n1+1][n2+1]的数组,第0行或者第0列就都赋值为0。

状态转移:

如果text2的第i个字符等于text1的第j个字符,那么dp[i][j] = dp[i-1][j-1]+1,前i-1个配前j-1个的情况下+1。如果不相等,那么dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

题解的做法也是类似,唯一不同的是我把字符串转换成了字符数组,速度快一点,但题目的字符串不是很大,不用也可以,以下是题解代码:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    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[m][n];
    }
}

之前写过一道类似的动态规划的题,比这道题要复杂很多,剑指offer19.正则表达式-CSDN博客

文章来源:https://blog.csdn.net/qq_61009660/article/details/135004825
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。