题目描述
分析
首先容易想出,dp数组的含义应该是两个字符串的最长公共子序列长度。
当两个字符串中的任意一个长度为0时,对应的LCS为0
由于同时受到两个数组的影响,所以dp数组应该设置为二维数组,
并且有:dp[i][j]代表的是s1的0-i的子序列与s2的0-j的子序列的LCS
然后分析递推公式:
调整ij的过程会出现三种情况:
1.s1[i] == s2[j]
在这种情况下,易得dp[i][j] == dp[i-1][j-1] + 1
2.两者不等的情况
在这种情况下,LCS仍然可能由于i和j向后的移动而增加。并且最多增加一个,但也可能都不增加
所以得到dp[i][j] == max(dp[i-1][j], dp[i][j-1])
在动态规划问题中,dp数组的定义,以及前后状态之间的关系是最重要的。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
vector<vector<int> > dp(s1.size()+1,vector<int>(s2.size()+1,0));
for(int i = 1; i <= s1.size(); i++){
for(int j = 1; j <= s2.size(); j++){
if(s1[i-1] == s2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout<<dp[s1.size()][s2.size()];
return 0;
}
标签:得学,LCS,套路,s2,s1,力扣,数组,序列,dp
From: https://www.cnblogs.com/satsuki26681534/p/18076406