题解 | #最长公共子序列(一)#
最长公共子序列(一)
https://www.nowcoder.com/practice/8cb175b803374e348a614e34b80ae191?tpId=196&tqId=39284&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196%26page%3D1%26search%3Dnc165&difficulty=undefined&judgeStatus=undefined&tags=&title=nc165
题意：
求两个字符串最长公共子序列的长度。
方法一：
动态规划
思路：dp[ i ][ j ]表示字符串s1的前 i 个字符与字符串s2的前 j 个字符的最长公共子序列的长度。状态转移方程如下：%3B%E2%80%8B)
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];
}
};
时间复杂度：%2C%E4%BA%8C%E9%87%8D%E5%BE%AA%E7%8E%AF%E3%80%82)
空间复杂度：%2C%E4%BA%8C%E7%BB%B4%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
java
思路：dp[ i ][ j ]表示字符串s1的前 i 个字符与字符串s2的前 j 个字符的最长公共子序列的长度。状态转移方程如下：
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];
}
}
时间复杂度：空间复杂度：
查看12道真题和解析