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

class Solution {
public:
    int dp[1005][1005];//dp[i][j]表示字符串s1的前i个字符与字符串s2的前j个字符的最长公共子序列的长度
    int LCS(string s1, string s2) {
        int len1=s1.size(),len2=s2.size();
        
        for(int i=1;i<=len1;i++){//二重循环
            for(int j=1;j<=len2;j++){
                if(s1[i-1]==s2[j-1]){//状态转移方程
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
};

import java.util.*;


public class Solution {
    
    public int LCS (String s1, String s2) {
        int len1=s1.length(),len2=s2.length();
        //dp[i][j]表示字符串s1的前i个字符与字符串s2的前j个字符的最长公共子序列的长度
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){//二重循环
            for(int j=1;j<=len2;j++){
                if(s1.charAt(i-1)==s2.charAt(j-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[len1][len2];
    }
}

时间复杂度：

空间复杂度：