点击打开链接
题目意思: 给定两个字符串求出最长公共子序列(注意和最长公共字串相区别)
解题思路: 动态规划(节省空间可以加上滚动数组)
根据最长公共子序列问题的性质,我们可以规定dp[i][j]为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1,那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。
1 ch1[i-1] = ch2[j-1] ,那么dp[i][j]= dp[i-1][j-1] + 1;
2 ch1[i-1] != ch2[j-1] ,那么我们知道ch1[i]和ch2[j]不可能在同一个公共子序列里出现,那么这个时候的最长的子序列可能以ch1[i]或ch2[j]结尾,那么由于dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};
这个时候所有i=0或j=0的dp[i][j]= 0;
0 ; i = 0或j= 0;
就有 dp = dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];
dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};i > 0且j> 0且ch1[i-1]!= ch2[j-1];
代码:有滚动数组
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 30010
char ch1[MAXN] , ch2[MAXN];
int dp[2][MAXN];//这里是压缩第一维,因为后面的for循环中j是一直变化的
int longest;
void solve(){
int i , j;
int len1 = strlen(ch1);
int len2 = strlen(ch2);
memset(dp , 0 , sizeof(dp)) ; longest = 0;
for(i = 1 ; i <= len1 ; i++){
for(j = 1 ; j <= len2 ; j++){
if(ch1[i-1] == ch2[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1]+1;
else dp[i%2][j] = dp[(i-1)%2][j]>dp[i%2][j-1]?dp[(i-1)%2][j]:dp[i%2][j-1];
if(dp[i%2][j] > longest) longest = dp[i%2][j];
}
}
printf("%d\n" , longest);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(gets(ch1)){
gets(ch2) ; solve();
}
return 0;
}
没用滚动数组
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 1010
char ch1[MAXN] , ch2[MAXN];
int dp[MAXN][MAXN];
int longest;
void solve(){
int i , j;
int len1 = strlen(ch1);
int len2 = strlen(ch2);
memset(dp , 0 , sizeof(dp)) ; longest = 0;
for(i = 1 ; i <= len1 ; i++){
for(j = 1 ; j <= len2 ; j++){
if(ch1[i-1] == ch2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
if(dp[i][j] > longest) longest = dp[i][j];
}
}
printf("%d\n" , longest);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(gets(ch1)){
gets(ch2) ; solve();
}
return 0;
}
分享到:
相关推荐
js js_leetcode题解之14-longest-common-prefix.js
c语言入门 C语言_leetcode题解之14-longest-common-prefix.c
这里提到的问题是求解两个字符串的最长公共子序列(Longest Common Subsequence, LCS)。这是一个经典的动态规划问题,对于理解和优化代码能力的考察非常有帮助。 最长公共子序列是指两个字符串中的一个子序列,它...
本题涉及的核心知识点是“最长公共子串”(Longest Common Substring),这是一个经典的动态规划问题。以下将详细解析这个问题及其解决方案。 首先,我们需要理解“最长公共子串”的概念。在两个给定的字符串s1和s2...
c c语言_leetcode 0014_longest_common_prefix.zip
java入门 java_leetcode题解之014_Longest_Common_Prefix
c语言入门 c语言_leetcode题解之1143_longest_common_subsequence
标题“POJ2533-Longest Ordered Subsequence”是指北京大学在线判题系统POJ上的一道编程题目,其核心任务是寻找一个序列中最长的有序子序列。描述中的“解题报告+AC代码”表明这个压缩包包含了对这道问题的解答思路...
c语言入门 c语言_leetcode题解03-longest-substring-without-repeating-characters
c语言入门 c语言_leetcode题解05-longest-palindromic-substring.c
js js_leetcode题解3-longest-substring-without-repeating-characters.js
javascript js_leetcode题解之128-longest-consecutive-sequence.js
javascript js_leetcode题解之159-longest-substring-with-at-most-two-distinct
js js_leetcode题解之32-longest-valid-parentheses.js
js js_leetcode题解之5-longest-palindromic-substring.js
c语言入门 C语言_leetcode题解之32-longest-valid-parentheses.c
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(n^2)】