1143. 最长公共子序列

我就是我 2022-12-07 15:21 216阅读 0赞

# 题目： #

[1143. 最长公共子序列][1143.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]  
[牛客网-\[编程题\]最长公共子序列][-]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]

# 题解：动态规划 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]

# 代码：动态规划 #

## 1. LeetCode代码： ##

public class code1143 { 
    
        public static int longestCommonSubsequence(String text1, String text2) { 
            int n1 = text1.length();
            int n2 = text2.length();
            // dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。
            int dp[][] = new int[n1 + 1][n2 + 1];
            for(int i = 1; i <= n1; i++)
            { 
                for(int j = 1; j <= n2; j++)
                { 
                    // 当 S1.i == S2.j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1.i 这个值，最长公共子序列长度加 1.
                    if(text1.charAt(i - 1) == text2.charAt(j - 1))
                    { 
                        dp[i][j] = dp[i- 1][j - 1] + 1;
                    }
                    // 当 S1.i != S2.j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者
                    else
                    { 
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            // 对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。
            return dp[n1][n2];
        }
    
        public static void main(String[] args) { 
            String text1 = "abcde";
            String text2 = "ace";
            int res = longestCommonSubsequence(text1, text2);
            System.out.println(res);
        }
    }

## 2. 牛客网代码： ##

public class 最长公共子序列 { 
    
        public static int findLCS(String A, int n, String B, int m) { 
            // dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。
            int dp[][] = new int[n + 1][m + 1];
            for(int i = 1; i <= n; i++)
            { 
                for(int j = 1; j <= m; j++)
                { 
                    // 当 S1.i == S2.j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1.i 这个值，最长公共子序列长度加 1.
                    if(A.charAt(i - 1) == B.charAt(j - 1))
                    { 
                        dp[i][j] = dp[i- 1][j - 1] + 1;
                    }
                    // 当 S1.i != S2.j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者
                    else
                    { 
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            // 对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。
            return dp[n][m];
        }
    
        public static void main(String[] args) { 
            String text1 = "1A2C3D4B56";
            int n = 10;
            String text2 = "B1D23CA45B6A";
            int m = 12;
            int res = findLCS(text1, n, text2, m);
            System.out.println(res);
        }
        
    }

# 参考： #

1.  [动态规划之最长公共子序列（LCS）][LCS]
2.  [动态规划图文解析（Java）][Java]
3.  [【你的衣服我扒了 - 《最长公共子序列》】动态规划 (1143. 最长公共子序列)][- _ _1143.]
4.  [动态规划解最长子序列子串等一类问题之最长公共子序列\[Hog Deer\]][Hog Deer]
5.  [超详细，动态规划解法][Link 1]
6.  [java 动态规划图文解析][java]
7.  [简单易懂 最长公共子序列][Link 2]
8.  [Marvel中等的学习笔记-1143][Marvel_-1143]
9.  [1143. 最长公共子序列][1143. 1]
10. [1143. 最长公共子序列][1143. 2]

[1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8d8174d1f22e49acb8c187518483386a.png
[-]: https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/99071b786e474349b20dc242a38e6ac8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/94e939bcc4c24e178ec84b0ab4d51271.png
[LCS]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/
[Java]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-tu-wen-jie-xi-by-yijiaoqian/
[- _ _1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/ni-de-yi-fu-wo-ba-liao-zui-chang-gong-gong-zi-xu-2/
[Hog Deer]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/a-fei-xue-suan-fa-zhi-by-a-fei-8/
[Link 1]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/chao-xiang-xi-dong-tai-gui-hua-jie-fa-by-shi-wei-h/
[java]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/java-dong-tai-gui-hua-tu-wen-jie-xi-by-sdwwld/
[Link 2]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/jian-dan-yi-dong-zui-chang-gong-gong-zi-xu-lie-by-/
[Marvel_-1143]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/marvelzhong-deng-de-xue-xi-bi-ji-1143-by-tyanyon-2/
[1143. 1]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/1143-zui-chang-gong-gong-zi-xu-lie-by-ming-zhi-sha/
[1143. 2]: https://leetcode-cn.com/problems/longest-common-subsequence/solution/1143-zui-chang-gong-gong-zi-xu-lie-by-alexer-660/