非递归方法解决最长公共子序列

解题思路:使用二维数组来记录相等的情况，根据左边和上方的数字以及相等的情况来为二维数组赋值

注意事项:起始项为【1，1】，所以要i-1，j-1；

参考代码:

#include <iostream>

#include <string>

#include <cmath>

int num[5000][5000];

using namespace std;

int main(){

int cnt=0;

string s1,s2;

    getline(cin,s1);

    getline(cin,s2);

int n=s1.size();

int m=s2.size();

for(int i=0;i<=n;i++){

for(int j=0;j<=m;j++){

if(i==0||j==0){

num[i][j]=0;

}

else if(s1[i-1]!=s2[j-1]){

num[i][j]=max(num[i-1][j],num[i][j-1]);

}

else if(s1[i-1]==s2[j-1]){

num[i][j]=num[i-1][j-1]+1;

}

}

}

    for(int i=0;i<=n;i++){

    for(int j=0;j<=m;j++){

    cnt=max(cnt,num[i][j]);

}

}

cout<<cnt<<endl;

return 0;

}