最长公共子序列动态规划法c++

以下是最长公共子序列（LCS）问题的动态规划解法的C++代码：

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

const int MAXN = 1005;

int dp[MAXN][MAXN];

int main()
{
    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.length(), m = s2.length();

    // 初始化边界条件
    for (int i = 0; i <= n; i++)
        dp[i][0] = 0;
    for (int j = 0; j <= m; j++)
        dp[0][j] = 0;

    // 动态规划求解
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // 输出最长公共子序列的长度
    cout << dp[n][m] << endl;

    return 0;
}

其中，`dp[i][j]`表示`s1`的前`i`个字符和`s2`的前`j`个字符的最长公共子序列长度。

初始化边界条件：当`s1`或`s2`的长度为0时，它们的最长公共子序列的长度为0。

动态转移方程：当`s1[i-1] == s2[j-1]`时，`dp[i][j] = dp[i-1][j-1] + 1`；否则，`dp[i][j] = max(dp[i-1][j], dp[i][j-1])`。