题解 | Coincidence

#include <iostream>
#include<cstring>
#include <string>
using namespace std;
const int N = 105;
int dp[N][N];


int main() {
    string a,b;
    while (cin>>a>>b) { 

        memset(dp,0,sizeof dp); //初始化dp

        a="#"+a; //在开头加一个无关紧要的字符。让真正的字符串从下标1开始
        b="#"+b;

        for(int i=1;i<a.size();i++){
            for(int j=1;j<b.size();j++){
                if(a[i]==b[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        cout<<dp[a.size()-1][b.size()-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

【动态规划法-算法思路】：

接下来介绍求解这个问题的动态规划方法，其时间复杂度只有 O(nm)：

1. 首先设置一个二维数组 dp[][]，令 dp[i][j]表示以 S1[i]作为末尾和以 S2[j]作为末尾的最长公共子序列的长度。因此，通过设置这个二维数组，最长公共子序列的长度便是数组dp[n][m]的值。根据 S1[i]和 S2[j]的关系可分为两种情况：
1. ① ==S1[i] = S2[j]==，即 S1 中的第 i 个字符和 S2 中的第 j 个字符相同，此时必定存在一个最长公共子串以 S1[i]和 S2[j]结尾，其他部分等价于 S1 中前 i-1 个字符和 S2 中前j-1 个字符的最长公共子串，于是这个子串的长度比 dp[i-1][j-1]多 1，即 dp[i][j] =dp[i-1][j-1] + 1。
2. ② ==S1[i] != S2[j]==，此时最长公共子串长度为dp[i-1][j]和dp[i][j-1]中的较大者，即在两种情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度而发生改变，也就是 dp[i][j] = max{dp[i-1][j], dp[i][j-1]}。
2. 从这两种情况可以得到状态转移方程：dp[i][j] = dp[i - 1][j - 1] + 1 (S1[i] = S2[j])dp[i][j] = max{dp[i − 1][y], dp[i][j − 1]}(S1[i] != S2[j])
3. dp[][]数组初始情况：若两个字符串其中一个为空串，那么公共字符串的长度必定为 0，于是可以得到：dp[i][0] = 0 (0 <= i <= n) dp[0][j] = 0 (0 <= j <= m)
4. 由这样的状态转移，只需依次遍历i和j便能求得各个dp[i][j]的值，其时间复杂度为O(nm)。最终 dp[n][m]中保存的值即为两个原始字符串的最长公共子序列长度。