最长公共子序列（动态规划）自用笔记

解题思路:
 

注意事项:
第一张原图里字符串前的""是特意留出的，可以理解为空，可以直接忽略不看，红笔是i，j的值从1开始，黑笔是数组下标。

第二张图是递归公式，C[i,j]代表LCS长度，例如C[1,2]中X1=Y2=a，所以C[1][2]=C[0][1]+1=1

C[1][3]=max(C[0][3],C[1][2])=1

参考代码:

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include <vector>
using namespace std;
int Max(string s1,string s2);
int main() {
    string s1,s2;
    cin >> s1 >> s2;
    Max(s1, s2);
    return 0;
}
int Max(string s1,string s2)
{
    int len1 = s1.size(),len2=s2.size(),maxlen;
    if (len1 > len2)
        maxlen = len1;
    else
        maxlen = len2;
    int dp[100][100]={0}; //矩阵初始全为0
    for (int i = 1; i <= len2 ; i++) //i代表len2即竖着的列（ace）
    {
        for (int j = 1; j <= len1 ; j++) //j代表len1即横着的行（babcde）

        {
        
            if ( s2[i-1]==s1[j-1] )//这里虽然i和j都是从1开始的，但是储存在数组里的字符串还是从下标0开始的！！！

                                            //由第一张图可得i=1对应a，j=1对应b。所以判断条件是s2[i-1]==s1[j-1]

            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            //cout << dp[i][j]<<" ";
        }
        //cout << endl;
    }
    cout << maxlen - dp[len2][len1];
    return 0;
}