51nod1006最長公共子序列LCS

輸出路徑的過程
結合dp數組和代碼一看就懂了
  a b d k s c a b
a 1 1 1 1 1 1 1 1 
b 1 2 2 2 2 2 2 2 
c 1 2 2 2 2 3 3 3 
i 1 2 2 2 2 3 3 3 
c 1 2 2 2 2 3 3 3 
b 1 2 2 2 2 3 3 4 
a 1 2 2 2 2 3 4 4      

經典的dp題，關鍵題目讓輸出最後的公共序列，可以通過判斷dp數組來從後往前找到狀态變化的字母，最後反序輸出

狀态轉移方程：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
const int N = 1e3 + 10;
const int M = 1e4 + 10;

int dp[N][N];
int main()
{
    string a, b, c = "";
    cin >> a >> b;
    for (int i = 1; i <= a.size(); i++) {
        for (int j = 1; j <= b.size(); j++) {
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    int i = a.size() - 1;
    int j = b.size() - 1;
    while(i >= 0 && j >= 0){
        if(a[i] == b[j]){
            c += a[i];
            i--;
            j--;
        }else if(dp[i][j+1] > dp[i+1][j]){
            i--;
        }else{
            j--;
        }
    }
    reverse(c.begin(), c.end());
    cout << c << endl;
    return 0;
}