問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1458思路:
額...最長公共子序列(LCS), 經典動態規劃(詳情見CLRS)
if(first[i] == second[j])
f(i, j) = f(i-1, j-1) + 1
else
f(i, j) = max(f(i-1, j), f(i, j-1))
1 int
2 dp_lcs()
3 {
4 int i, j;
5 for(i=0; i<=m; i++)
6 table[i][0] = 0;
7 for(j=0; j<=n; j++)
8 table[0][j] = 0;
9
10 for(i=1; i<=m; i++) {
11 for(j=1; j<=n; j++) {
12 if(fst[i-1] == snd[j-1])
13 table[i][j] = table[i-1][j-1] + 1;
14 else
15 table[i][j] = max(table[i-1][j], table[i][j-1]);
16 }
17 }
18 return table[m][n];
19 }