要求：

掌握動態(tài)規(guī)劃法的思想，及動態(tài)規(guī)劃法在實際中的應(yīng)用投慈；分析最長公共子序列的問題特征，選擇算法策略并設(shè)計具體算法呀狼，編程實現(xiàn)兩輸入序列的比較等曼，并輸出它們的最長子序列

算法解析：

令dp[i][j]表示字符串A的i號位和字符串B的j號位之前的LCS長度里烦，可以根據(jù)兩個字符串的情況分為兩種策略
1、 若A[i]=B[j]禁谦，則字符串A與字符串B的LCS增加1位胁黑，即有dp[i][j]=dp[i-1][j-1]+1
2、 若A[i]!=B[j],則LCS無法延長州泊，因此dp[i][j]=max(dp[i-1][j],dp[i][j-1])

邊界：dp[0][j]=dp[i][0]=0
Tips:輸入的兩個字符串A丧蘸、B下標(biāo)是從0開始，那么就會要尋找dp[-1]的情況遥皂，這是需要處理的

• 讓數(shù)組A力喷、B從下標(biāo)1開始讀入，利用c語言的gets(A+1)可以實現(xiàn)演训，但由于該函數(shù)并不安全所以在最新的ide中已被棄用弟孟，所以可以再建兩個數(shù)組來承接AB來實現(xiàn)下標(biāo)為1，但這樣會造成開銷
• 讓轉(zhuǎn)移矩陣變形样悟，dp[i+1][j+1]=dp[i][j]+1,相當(dāng)于把原來的元素全部向前移一個單位拂募，這樣dp[0][]就可以表現(xiàn)為A[0]之前的LCS長度

代碼：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string A, B;
int dp[12][12];
int C[100][100];
stack<char> same;
int main() {
    int n;
    cin >> A;
    cin >> B;
    for (int i = 0; i <= A.length(); i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= B.length(); j++) {
        dp[0][j] = 0;
    }
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            if (A[i] == B[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                C[i + 1][j + 1] = 1;
            }
            else if(dp[i][j+1]>=dp[i+1][j]){
                dp[i + 1][j + 1] = dp[i][j + 1];
                C[i + 1][j + 1] = 2;
            }
            else {
                dp[i + 1][j + 1] = dp[i+1][j];
                C[i + 1][j + 1] = 3;
            }
        }
    }
    for (int i = A.length(), j = B.length(); i >= 0 && j >= 0;) {
        if (C[i][j] == 1) {
            i--;
            j--;
            same.push(A[i]);
        }
        else if (C[i][j] == 2) {
            i--;
        }
        else {
            j--;
        }
    }
    cout << dp[A.length()][B.length()] << endl;
    while(!same.empty()){
        cout << same.top();
        same.pop();
    }
    return 0;
}

樣例：

輸出.png

如有錯誤庭猩，歡迎斧正