Junior Dynamic Programming——动态规划初步·各种子序列问题

给定两个串\(A\)，\(B\)，求最长公共子序列

我们可以用\(dp[i][j]\)来表示第一个串的前\(i\)位，第二个串的前\(j\)位的LCS的长度，那么我们是很容易想到状态转移方程的：

• 如果当前的\(A[i]\)和\(B[j]\)相同（即是有新的公共元素） 那么\(dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1)\);
• 如果不相同，即无法更新公共元素，考虑继承：\(dp[i][j]=max(dp[i−1][j],dp[i][j−1])\)

写出以下代码

#include <iostream>
using namespace std;
int dp[1001][1001], a1[2001], a2[2001], n, m;
int main() {
    //dp[i][j]表示两个串从头开始，直到第一个串的第i位
    //和第二个串的第j位最多有多少个公共子元素
    cin >> n >> m;
    for (int i = 1; i <= n; i++)scanf("%d", &a1[i]);
    for (int i = 1; i <= m; i++)scanf("%d", &a2[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (a1[i] == a2[j])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            //因为更新，所以++；
        }
    cout << dp[n][m];
}

对于本题，需要考虑\(O(nlogn)\)做法，请参考题解开头给的博客链接。