使用例題：最長公共子序列（原題鏈接）

題意：

?????給你兩個字符串text1，text2，求兩串字符串中的共有最長字序列。

代碼詳解：

int longestCommonSubsequence(string text1, string text2) {
    const int N=1e3+10;
    //初始化為0
    int dp[N][N]={0};
    int n=text1.size();
    int m=text2.size();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
        	//i-1因為字符串從0開始記數
            //倘若字符相同，則字符共有個數加一
            if (text1[i-1]==text2[j-1])dp[i][j]=dp[i-1][j-1]+1;
            //否則考慮不取text1末的字符的情況，或不取text2字符末的情況
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[n][m];
}

問題一：

?????為什么max里只存在兩種情況？

?????原因：當兩個字符出現不同時，說明此時兩個字符串中的字符需要考慮取其中一個選取，此時存在兩種情況，1.不取text1字符串的末尾，2.不取text2字符串的末尾，即dp[i-1][j]和dp[i][j-1]兩種情況。假設比較dp[i-1][j-1]代表同時舍棄兩個字符，此時相當于沒做出改變。

問題二：

?????編寫代碼輸出最長公共子序列的長度和其中一個最長公共子序列。

?????本代碼采用遞推的形式，因為查找的代碼從左上至右下，所以可以使用從右下至左上的形式輸出，因此代碼的移動方式分為三種，即當字符不相同時，比較上邊和左邊的值，當字符相同時，移至左上，并輸出字符。

void print(int i, int j){
	//當a或者b的長度完全跑完時，停止代碼
    if(i == 0 || j == 0)return;
    //優(yōu)先考慮格子內字符不同的情況，避免因為過早滿足判斷字符相同情況而暴斃
    if(dp[i][j]==dp[i-1][j])print(i-1,j);//考慮上邊格子符合條件
    else if (dp[i][j]==dp[i][j-1])print(i,j-1);//考慮左邊代碼是否符合
    else if(dp[i][j]==dp[i-1][j-1]+1)
    {
    	//符合則移至左上
        print(i-1,j-1);
        cout<<a[i-1];
    }
}

問題三：

?????請使用滾動數組壓縮空間、計算最長公共子序列方案數。（核對鏈接）

?????首先先解決如何計算最長公共子序列的方案數，依據遞推的思維，從代碼的移動方式可知，存在三種移動方式，因此可以推出當前的方案數由上一步的方案數推移得到。但此時， 存在一種特殊情況，即dp[i-1][j]和dp[i][j-1]都來自dp[i-1][j-1]時，代碼存在重復操作，因此需要進行特殊判斷，當滿足該條件時，減去dp[i-1][j-1]。

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

const int N=1e6+10,M=1e8;
//使用滾定數組壓縮空間
int dp[2][N]={0},ans[2][N];
string a,b;


int main(){
    cin >>a>>b;
    int n=a.size();
    int m=b.size();
    //題意中，字符串末存在'.'
    n--;
    m--;
    //初始化方案數
    for (int i=0;i<=m;i++)ans[0][i]=1;
    ans[1][0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
        	//初始化方案數，避免不能使用的情況
            ans[i & 1][j]=0;
            if (a[i-1]==b[j-1])
            {
                dp[i & 1][j]=dp[i-1 & 1][j-1]+1;
                //當字符相同，方案來源于左上
                ans[i & 1][j]+=ans[i-1 & 1][j-1];
            }
            else dp[i & 1][j]=max(dp[i-1 & 1][j],dp[i & 1][j-1]);
            //字符不相同，判斷左邊和上邊兩個的方案來源
            if (dp[i & 1][j]==dp[i & 1][j-1])ans[i & 1][j]+=ans[i & 1][j-1];
            if (dp[i & 1][j]==dp[i-1 & 1][j])ans[i & 1][j]+=ans[i-1 & 1][j];
            //特判來源特殊情況
            if (a[i-1] != b[j-1] && dp[i & 1][j]==dp[i-1 & 1][j-1])ans[i & 1][j]-=ans[i-1 & 1][j-1];
            ans[i & 1][j]=ans[i & 1][j]%M;
        }
    }
    //判斷滾動數組，最后存入的結果是在1，還是0
    if (n & 1)cout <<dp[1][m]<<"\n"<<ans[1][m]<<"\n";
    else cout <<dp[0][m]<<"\n"<<ans[0][m]<<"\n";
    return 0;
}