分析:
d[i][j]表示a[1],a[2]……a[i] 和b[1],b[2]……b[i]的最长上升子序列长度.while(a[i]==a[j]) d[i][j]=d[i-1][j-1]+1; else d[i][j]=max{d[i-1][j],d[i][j-1]}; 时间复杂度为o(n*m).
代码及简要分析: View Code
1 #include2 #include 3 #include 4 #include //使用cin>>输入需要加上此头文件 5 using namespace std; 6 string a,b; 7 int dp[1000][1000]; 8 int max(int x,int y) 9 {10 if(x>=y)11 return x;12 else13 return y;14 }15 16 int main()17 {18 int i,j;19 while(cin>>a)20 {21 cin>>b;22 memset(dp,0,sizeof(dp));//ddp[i][j]为a[0]...a[i]和b[0]...b[j]的最长公共子序列的长度。23 for(i=0;i