描述

给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 1≤m,n≤10001\leq m,n\leq 10001≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度 O(mn)O(mn)O(mn)，时间复杂度 O(mn)O(mn)O(mn)
进阶：空间复杂度 O(min(m,n))O(min(m,n))O(min(m,n))，时间复杂度 O(mn)O(mn)O(mn)

输入描述：

第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。

输出描述：

输出两个字符串的最长公共子序列的长度

示例1

输入： 
5 6
abcde
bdcaaa
输出： 
2
说明： 
最长公共子序列为 "bc" 或 "bd" ，长度为2   

示例2

输入： 
3 3
abc
xyz
输出： 
0

    cpp： 

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
    
public:
    int longestSeqNum(string &s, string &t){
        int m = s.size();
        int n = t.size();
        vector<vector<uint64_t>>dp(m+1,vector<uint64_t>(n+1,0));// dp[i][j] 表示 i-1结尾的s j-1结尾 t的
        // 最长公共 子序列的长度
        // 注意要弄懂 dp[i][j] 的含义 不要有 dp[0][0] = 1; 这什么鬼
        for (int i =1;i<=m;i++){
            for(int j =1;j<= n;j++){
                
                if(s[i-1] ==t[j-1]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
        
    }
    
};

int main(){
    
    int n,m;
    string s,t;
    // 题目输入格式
    cin >> n >> m;
    cin >> s>> t;
    
    Solution solu;
    cout<< solu.longestSeqNum(s,t) <<endl;
    
    
    return 0;
}