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

题意整理

• 给定两个字符串s1和s2。
• 求这两个字符串的最长公共子序列的长度。

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i][j]dp[i][j]$表示s1长度为i，s2长度为j时的最长公共子序列的长度。
• 状态初始化：初始阿长度均为0。
• 状态转移：两层循环遍历s1和s2中每一个字符。若当前字符相等，则由之前的最长公共子序列加1。即$dp[i+1][j+1]=dp[i][j]+1dp[i+1][j+1]=dp[i][j]+1$。否则，取dp[i][j+1]、dp[i+1][j]两者中较大值。即$dp[i+1][j+1]=Math\mathrm{.}max(dp[i][j+1],dp[i+1][j])dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j])$。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    public int LCS (String s1, String s2) {
        //转化为字符数组
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        int m=arr1.length;
        int n=arr2.length;
        //dp[i][j]表示s1、s2长度分别为i、j时对应的最长公共子序列长度
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(arr1[i]==arr2[j]){
                    //如果相等，则由之前的最长公共子序列加1
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else{
                    //否则取dp[i][j+1]、dp[i+1][j]两者中较大值
                    dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$m\ast nm*n$次，所以时间复杂度是$O(m\ast n)O(m*n)$。
• 空间复杂度：需要额外大小为$(m+1)\ast (n+1)(m+1)*(n+1)$的dp数组，所以空间复杂度为$O(m\ast n)O(m*n)$。

方法二（空间优化）

1.解题思路

思路和方法一和差不多。按照方法一的状态转移，每次当前字符相当时，只与前一个最大长度的状态相关，所以可以利用滚动变量的思路，记录上一次的最大长度的状态。从而只需要一维空间的dp数组。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    public int LCS (String s1, String s2) {
        //转化为字符数组
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        int m=arr1.length;
        int n=arr2.length;
        //dp[i]表示s2长度为i时，与s1的最长公共子序列长度
        int[] dp=new int[n+1];
        
        for(int i=0;i<m;i++){
            //记录之前的最长公共子序列的长度
            int pre=0;
            for(int j=0;j<n;j++){
                int cur=dp[j+1];
                //如果相等，则由之前的最长公共子序列加1
                if(arr1[i]==arr2[j]){
                    dp[j+1]=pre+1;
                }
                //如果不等，取两者较大者
                else{
                    dp[j+1]=Math.max(dp[j],dp[j+1]);
                }
                pre=cur;
            }
        }
        return dp[n];
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$m\ast nm*n$次，所以时间复杂度是$O(m\ast n)O(m*n)$。
• 空间复杂度：需要额外大小为n+1的dp数组，所以空间复杂度为$O(n)O(n)$。