题解 | #Common Subsequence#

最长公共子序列（m,n）
dp方程：
dp[i][j] = dp[i-1][j-1] +1  (str1[i]==str2[j])
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) (str1[i]!=str2[j])
注意这个操作，使ij个元素与索引对应
str1 = " "+str1;
str2 = " "+str2;

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    string str1;
    string str2;
    while(cin>>str1&&cin>>str2){
        str1 = " "+str1;
        str2 = " "+str2;
        int dp[str1.length()][str2.length()];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<str1.length();i++){
            for(int j=0;j<str2.length();j++){
                if(i==0||j==0) {dp[i][j]=0; continue;}
                else if(str1[i]==str2[j]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        cout<<dp[str1.length()-1][str2.length()-1]<<"\n";
    }
}