【LeetCode: 1143. 最长公共子序列 | 暴力递归=＞记忆化搜索=＞动态规划】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 1143. 最长公共子序列

⛲ 题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

🌟 求解思路&实现代码&运行结果

⚡ 暴力递归

🥦 求解思路

1. 最长公共子序列问题怎么求解呢？这道题目的求解思路也比较简单，我们通过记录俩个字符串位置元素的下标，一个一个去遍历元素，判断对应位置上的元素是否想等，如果相等，俩个指针同时向右移动，继续下一个位置的判断。否则，我们可以让指向字符串1的指针向右移动去和当前指向字符串2的指针判断此时位置的元素是否相等，或者，我们可以让指向字符串2的指针向右移动去和当前指向字符串1的指针判断此时位置的元素是否相等，取它们二者的最大值。
2. 为什么可以使用递归解决这个问题呢？因为问题的规模可以进行拆解，大问题和小问题都是执行同样的操作，比如此时字符串1和字符串2它们0位置的元素都相等了，那么我们同时向后移动，去判断下一个位置是否相同。
3. 以上就是该题目的求解思路，我们来一起看一下具体实现的代码。

🥦 实现代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] arr1=text1.toCharArray();
        char[] arr2=text2.toCharArray();
        return process(0,0,arr1,arr2);
    }

    public int process(int i,int j,char[] arr1,char[] arr2){
        if(i>=arr1.length||j>=arr2.length) return 0;
        if(arr1[i]==arr2[j]){
            return process(i+1,j+1,arr1,arr2)+1;
        }
        return Math.max(process(i+1,j,arr1,arr2),process(i,j+1,arr1,arr2));
    }
}

🥦 运行结果

不出我们所料，超出时间限制，怎么办呢？各位看官，不要紧，我们继续向下看。

⚡ 记忆化搜索

🥦 求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

🥦 实现代码

class Solution {
    int[][] dp;
    public int longestCommonSubsequence(String text1, String text2) {
        char[] arr1=text1.toCharArray();
        char[] arr2=text2.toCharArray();
        int n=arr1.length,m=arr2.length;
        dp=new int[n][m];
        for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);
        return process(0,0,arr1,arr2);
    }

    public int process(int i,int j,char[] arr1,char[] arr2){
        if(i>=arr1.length||j>=arr2.length) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(arr1[i]==arr2[j]){
            return dp[i][j]=process(i+1,j+1,arr1,arr2)+1;
        }
        return dp[i][j]=Math.max(process(i+1,j,arr1,arr2),process(i,j+1,arr1,arr2));
    }
}

🥦 运行结果

我们可以看到，此时的记忆化搜索已经通过了！！！

⚡ 动态规划

🥦 求解思路

1. 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。

🥦 实现代码

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

🥦 运行结果

💬 共勉