【題目鏈接】

ybt 1265：【例9.9】最長公共子序列

【題目考點(diǎn)】

1. 動態(tài)規(guī)劃：線性動規(guī)

• 最長公共子序列

【解題思路】

1. 狀態(tài)定義

集合：X、Y兩序列的公共子序列
限制：子序列在X，Y中存在的區(qū)間（前多少個元素）
屬性：長度
條件：最大
統(tǒng)計(jì)量：長度
狀態(tài)定義：dp[i][j]表示X序列的前i個元素與Y序列的前j個元素的最長公共子序列的長度。
初始狀態(tài)：
X序列前i個元素與Y序列前0個元素的最長公共子序列的長度為0：dp[i][0]=0
X序列前0個元素與Y序列前j個元素的最長公共子序列的長度為0：dp[0][j]=0

2. 狀態(tài)轉(zhuǎn)移方程

記$X_i$表示X序列的前i個元素構(gòu)成的子序列。$Y_j$表示Y序列的前j個元素構(gòu)成的子序列。x[i]為X序列的第i個元素，y[j]為Y序列的第j個元素
分割集合：$X_i$與$Y_j$兩序列的公共子序列

• 如果x[i]等于y[j]，那么x[i]（或y[j])一定是$X_i$與$Y_j$的最長公共子序列的最后一個元素。該最長公共子序列是由$X_{i?1}$與$Y_{j?1}$兩序列的最長公共子序列后面添加x[i]得到的，長度為：dp[i][j] = dp[i-1][j-1]+1
• 如果x[i]不等于y[j]
  • 如果x[i]不作為 $X_i$與$Y_j$的最長公共子序列的最后一個元素，那么$X_i$與$Y_j$的最長公共子序列就是$X_{i?1}$與$Y_j$的最長公共子序列，長度為dp[i][j] = dp[i-1][j]
  • 如果y[j]不作為 $X_i$與$Y_j$的最長公共子序列的最后一個元素，那么$X_i$與$Y_j$的最長公共子序列就是$X_i$與$Y_{j?1}$的最長公共子序列，長度為dp[i][j] = dp[i][j-1]
  • 以上兩種情況取最大值。

【題解代碼】

寫法1：線性動規(guī)

#include <bits/stdc++.h> using namespace std; #define N 1005 int dp[N][N]; int main() {string x, y;cin >> x >> y; int lx = x.length(), ly = y.length();for(int i = 1; i <= lx; ++i)for(int j = 1; j <= ly; ++j){if(x[i-1] == y[j-1])//i,j下標(biāo)從1開始 轉(zhuǎn)為 x，y下標(biāo)從0開始 dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}cout << dp[lx][ly] << endl; return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1265：【例9.9】最长公共子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。