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

int main(){
    string a,b;
    while(cin>>a>>b){
        int n=a.size(),m=b.size();
        std::vector<vector<int>> dp(n+1,vector<int>(m+1));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j]=max(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;
    }
}

本题的目标是求最长离散子序列的结果的问题，dp的状态两个字符串到该位置的时候当前的最佳和，假如两个字符串当前字符相同，问题收缩为之前的最大问题，假如不相同，我们取过去的值，因为存在两个方向，所以取两个方向的前者最大值。

其中的等于判定是为了完备性，如果你改成下面的代码，也是能过的，因为我们逻辑上思考可以发现，他是只会向前的。

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

int main(){
    string a,b;
    while(cin>>a>>b){
        int n=a.size(),m=b.size();
        std::vector<vector<int>> dp(n+1,vector<int>(m+1));
...