动态规划——最长公共子序列（LCS）

最长公共子序列的问题描述为：

下面介绍动态规划的做法。

令 dp[i][j]表示字符串 A的 i号位与字符串 B的j号位之前的 LCS长度（下标从 1开始），如 dp[4][5]表示 "sads"与 “admin"的 LCS长度。那么可以根据 A[i]和 B[j]的情况，分为两种决策:

若 A[i]==B[j]，则字符串 A与字符串 B的 LCS增加了 1位，即有 dp[i][j]=dp[i-1][j-1]+1。若 A[i] != B[j]，则字符串 A的 i号位和字符串B的 j号位之前的 LCS无法延长，因此 dp[i][j]将会继承 dp[i-1][j]与 dp[i][j-1]中的较大值,即有 dp[i][j]=max{dp[i-1][j], dp[i][j-1]}。

由此可以得到状态转移方程：

$dp[i][j]=\left\{\begin{matrix}dp[i-1][j-1]+1,A[i]==B[j]\\ max\left \{ dp[i-1][j], dp[i][j-1] \right\},A[i]!=B[j]\end{matrix}\right.$

边界：dp[i][0] = dp[0][j] = 0 (0≤i≤n, 0≤j≤m)

这样状态 dp[i][j]只与其之前的状态有关，由边界出发即可得到整个 dp数组，最终 dp[n][m]就是需要的答案，时间复杂度为 O(nm)。

代码如下：

1 /* 2最长公共子序列（LCS） 3 */ 4 5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include <time.h>10 #include <stdbool.h>11 12 #define maxn 10013 char A[maxn], B[maxn];14 int dp[maxn][maxn]; 15 16 // 求较大值17 int max(int a, int b) {18return a>b ? a : b; 19 } 20 21 int main() {22scanf("%s %s", A+1, B+1); // 从下标为 1 开始输入 23int lenA = strlen(A+1); // 读取长度也从 1 开始 24int lenB = strlen(B+1);25int i, j;26for(i=0; i<=lenA; ++i) { // 边界 27 dp[i][0] = 0;28} 29for(j=0; j<=lenB; ++j) {30 dp[0][j] = 0;31}32for(i=1; i<=lenA; ++i) { // 状态转移方程 33 for(j=1; j<=lenB; ++j) {34 if(A[i] == B[j]) {35 dp[i][j] = dp[i-1][j-1] + 1;36 } else {37 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);38 }39 }40}41printf("%d\n", dp[lenA][lenB]); // dp[lenA][lenB] 是答案 42 43return 0;44 }