用动态规划法求解公共子序列问题c++

公共子序列问题是经典的动态规划问题之一，可以用DP算法求解。下面是C++代码实现：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+10;
int dp[N][N];

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

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

    // 初始化
    for(int i = 1; i <= n; i++)
        dp[i][0] = 0;
    for(int i = 1; i <= m; i++)
        dp[0][i] = 0;

    // DP转移
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(s1[i-1] == s2[j-1]) // s1和s2的下标都要减1
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }

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

上述代码中，`dp[i][j]`表示s1的前i个字符和s2的前j个字符的最长公共子序列长度。初始化时，`dp[i][0]`和`dp[0][j]`均为0，因为s1的前0个字符和s2的前0个字符的最长公共子序列长度为0。DP转移时，如果s1的第i个字符和s2的第j个字符相等，那么`dp[i][j]`就等于`s1`的前`i-1`个字符和`s2`的前`j-1`个字符的最长公共子序列长度加1，否则`dp[i][j]`就等于`s1`的前`i-1`个字符和`s2`的前`j`个字符的最长公共子序列长度与`s1`的前`i`个字符和`s2`的前`j-1`个字符的最长公共子序列长度的较大值。最后输出`dp[n][m]`就是s1和s2的最长公共子序列长度。