給定兩個(gè)序列，求兩個(gè)序列的最長(zhǎng)公共子序列的長(zhǎng)度（暫時(shí)先列出來長(zhǎng)度好了……）
如此經(jīng)典的DP，我竟然現(xiàn)在才弄明白，真心弱爆了，好吧，廢話不說了，開始吧。
對(duì)于兩個(gè)序列，dp[i][j]表示當(dāng)?shù)谝粋€(gè)序列取前i個(gè)元素，第二個(gè)序列取前j個(gè)元素的時(shí)候，最長(zhǎng)公共子序列的長(zhǎng)度，那么對(duì)于此狀態(tài)，有如下幾種推導(dǎo)方式，假設(shè)第一個(gè)序列是X（x1,x2...xi），第二個(gè)序列是Y（y1,y2...yj），如果xi=yj，則dp[i][j]=dp[i-1][j-1]+1，否則，就等于dp[i-1][j]或者dp[i][j-1]。理由如下，假設(shè)X和Y的最長(zhǎng)公共子序列為Z（z1,z2,...zk），如果xi=yj，必然有xi=yj=zk，如果xi≠yj，而且xi≠zk，則Z必然是Xi-1和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閤i存在與否根本不影響最終的結(jié)果，而zk必然存在于X的前i-1個(gè)元素中，否則不成立，同理可運(yùn)用于Y序列，所以可以得到推導(dǎo)關(guān)系。
剛剛把代碼YY出來，不知道對(duì)不對(duì)，希望某一個(gè)大牛出來指正一下……
特別鳴謝：磊哥ZLGG
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 int max(int a, int b)
6 {
7 if (a > b) return a;
8 else return b;
9 }
10 int main()
11 {
12 char x[101], y[101];
13 int lx, ly, i, j, dp[100][100];
14 cin >> x;
15 cin >> y;
16 lx = strlen(x);
17 ly = strlen(y);
18 for (i = 1; i <= lx; i++)
19 for (j = 1; j <= ly; j++)
20 {
21 if (x[i] == y[j]) dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][j - 1]));
22 else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
23 }
24 cout << dp[lx][ly] << endl;
25 return 0;
26 }
2