c++实现动态规划算法求解最长公共子序列问题

以下是C++代码实现动态规划算法求解最长公共子序列问题：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
char s1[MAXN], s2[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> s1+1 >> s2+1;    // 注意字符串下标从1开始
    int len1 = strlen(s1+1), len2 = strlen(s2+1);

    // 初始化边界条件
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    // 输出最长公共子序列
    int i = len1, j = len2;
    while (i > 0 && j > 0) {
        if (s1[i] == s2[j]) {
            cout << s1[i];
            --i, --j;
        } else {
            if (dp[i-1][j] > dp[i][j-1]) {
                --i;
            } else {
                --j;
            }
        }
    }
    cout << endl;

    return 0;
}

其中，dp[i][j]表示s1串前i个字符和s2串前j个字符的最长公共子序列长度。边界条件为dp[i][0]=0和dp[0][j]=0，表示空串与任意字符串的最长公共子序列长度为0。转移方程为：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & \text{if } s1_i=s2_j \ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} $$

最后，从dp[len1][len2]开始，根据转移方程逆推出最长公共子序列即可