A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, …, xm > another sequence Z = < z1, z2, …, zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, …, ik > of indices of X such that for all j = 1,2,…,k, x ij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the PRoblem is to find the length of the maximum-length common subsequence of X and Y. Input The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. Output For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0
求最长公共子序列 状态转移方程 dp[i][j] 是在i的当前字符，和j的当前字符相对于前面 1~i-1 1~j-1里面最长的公共子序列。 因为题目要求的公共子序列的两个条件是 在s里面是有次序的，在s2里面也是有次序，过了的不能再被选择，只能不断往后选。相当于两个上升序列合并，但是选择条件改变了。而那些不相同的 保持的是上一个相同的最大值。 遇到两个相同的值，dp[i][j] 由s的上一个字符阶段 i-1 里面选择 j在1~j-1字符里面的最长公共序列里面选择最长的dp，由于j-1是j在 1到j-1里面最长的 所以 dp[i-1][j-1]是上一个相同字符里面最长的。 为什么j-1 是1~j-1里面最长的 因为 dp[i][j] =max(dp[i-1][j],dp[i-1][j-1]),从而得到无论是i的上一阶段还是当前阶段i也是最长的，而且 与（1~j-1）也是最长的那个。 if(s[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1; else { dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}
#include <cstdio>#include <iostream>#include <cstring>using namespace std;int dp[1001][1001];char s[1001];char s1[1001];//if(s[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;//dp[i][j]=max(dp[i-1][j],dp[i][j-1]);int main(){ while(scanf("%s %s",s+1,s1+1)!=EOF) { memset(dp,0,sizeof(dp)); dp[0][0]=0; int len1=strlen(s+1); int len2=strlen(s1+1); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(s[i]==s1[j]) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } printf("%d/n",dp[len1][len2] ); }}新闻热点
疑难解答
