動態規劃求最長公共子序列和子序列具體是什麼

**子序列與子串是兩種不同的概念，千萬不要混淆
給定字串"tzjnbblmp";

子串是tzj,bbln等,子串是連在一起的

子序列是 tjn,nlmp等，但是子序列中的字元在字串中不一定是連在一起的。
但是順序在原串是不可顛倒的，比如pml既不是子序列，也不是子串
**
回到正文

什麼是最長公共子序列
就是兩個字串的最長的公共的子序列
例如s1=「wxhnwq」,s2=「xppwyq」
最長子序列就是"xwq"

我們這樣很容易看出來，但是計算機怎麼知道吶，
動態規劃吧；
設dp[i][j]表示長度為i的字串與長度為j的字串的最長的公共子序列
我們分兩種情況
1.s1[i]==s2[j],我們就轉移方程，dp[i][j]=dp[i-1][j-1]+1;意思是，以s1[i],s2[j]結尾的字串的最大長度，肯定是前面的，在加上新加入的；
2.s1[i]!=s2[j],dp[i][j]=max(dp[i-1][j],dp[i][j-1];意思是，我們選擇（長度為i與j-1）與（長度為i-1與j）的大的一個
我們遞迴求子序列是什麼，在轉移方程的同時，標記這一步是由i-1，j-1
還是i，j-1
還是i-1，j
來的

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
typedef long long ll;
int dp[1000][1000];
int vis[1001][1001];
char a[100];
char b[100];
void lcslength(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        if(a[i]==b[j])
        {
            dp[i][j]=dp[i-1][j-1]+1;
            vis[i][j]=1;

        }
        else if(dp[i-1][j]>dp[i][j-1])
        {
            dp[i][j]=dp[i-1][j];
            vis[i][j]=2;
        }
        else if(dp[i-1][j]<=dp[i][j-1])
        {
            dp[i][j]=dp[i][j-1];
            vis[i][j]=3;
        }
    }
}
void lcs(int n,int m)
{
    if(n==0 || m==0)
        return;
    if(vis[n][m]==1)
        lcs(n-1,m-1),cout<<a[n]<<" ";
    if(vis[n][m]==2)
        lcs(n-1,m);
    if(vis[n][m]==3)
        lcs(n,m-1);
}
int main()
{
  string s1,s2;
   cin>>s1>>s2;
   int n=s1.length();
   int m=s2.length();
   for(int i=1;i<=n;i++)
      a[i]=s1[i-1];
   for(int i=1;i<=m;i++)
      b[i]=s2[i-1];
   lcslength(n,m);
   cout<<dp[n][m]<<endl;
  lcs(n,m);
    return 0;
}