LCS

#include<iostream>
#include<cstring>
const int MAXN = 100;
using namespace std;
char x[MAXN] = "abcbdab";
char y[MAXN] = "bdcaba";
int dp[MAXN][MAXN] = {0}; //dp[i,j]:Xi与Yj的LCS的长度
int b[MAXN][MAXN] = {0}; //标记函数 -1:向左 1:斜向上 0:向上
int main(){
    int m = strlen(x), n = strlen(y);
    //初始化边界值
    for(int i = 0; i < m; i++)
        if(x[i]==y[0]) dp[i][0] = 1;
    for(int j = 0; j < n; j++)
        if(x[0]==y[j]) dp[0][j] = 1;
    //迭代求解
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            if(x[i]==y[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                b[i][j] = 1;
            }
            else if( dp[i-1][j] <= dp[i][j-1] ){
                dp[i][j] = dp[i][j-1];
                b[i][j] = -1;
            } else dp[i][j] = dp[i-1][j];
        }
    } //时间复杂度O(mn) 空间复杂度O(mn)
    cout<<dp[m-1][n-1]<<endl;
    return 0;
}