MOOC程式設計與算法練習題——動态規劃#2806最長子序列

描述

我們稱序列Z = < z1, z2, …, zk >是序列X = < x1, x2, …, xm >的子序列當且僅當存在 嚴格上升 的序列< i1, i2, …, ik >，使得對j = 1, 2, … ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。

現在給出兩個序列X和Y，你的任務是找到X和Y的最大公共子序列，也就是說要找到一個最長的序列Z，使得Z既是X的子序列也是Y的子序列。

輸入

輸入包括多組測試資料。每組資料包括一行，給出兩個長度不超過200的字元串，表示兩個序列。兩個字元串之間由若幹個空格隔開。

輸出

對每組輸入資料，輸出一行，給出兩個序列的最大公共子序列的長度。

樣例輸入

abcfbc abfcab

programming contest

abcd mnp

樣例輸出

4

2

難點還是确定子問題，這裡使用maxlen[ i ][ j ]作為狀态，表示長度為i的串和長度為j的串的最長公共子序列長度。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 210
int maxlen[MAX][MAX];
int main(){
	char s1[MAX],s2[MAX];
	while(cin >> s1 >> s2){
		int i,j;
		int s1len = strlen(s1);
		int s2len = strlen(s2);
		for(i = 0;i <= s1len; ++i){//邊界條件
			maxlen[0][i] = 0;
			maxlen[i][0] = 0;
		}
		for(i = 1;i <= s1len; ++i){
			for(j = 1;j <= s2len; ++j){//遞推式：從第一行開始逐行遞推
				if(s1[i-1] == s2[j-1])
					maxlen[i][j] = maxlen[i-1][j-1] + 1;
				else{
					maxlen[i][j] = max(maxlen[i-1][j],maxlen[i][j-1]);
				}
			}
		}
		cout << maxlen[s1len][s2len] << endl;
	}
	return 0;
}