非常简单的DP

如果dp[i,j]表示从0到i 和 从0到j 这两段的相似度，

那么可以知道每个dp[i,j]是由三种状态转化过来的

第一种 当dna1[i]==dna2[j]的时候

 

dp[i-1,j-1] +  1  长度加1

第二种  否则 从下面两个状态过来那就是

dp[i][j-1] 和 dp[i-1][j]//注意因为是顺序遍历 这两个都已经计算过

取两者最大即可。

#include 
     
      #include 
      
       #include 
       
        using namespace std;//最长公共子序列长度 LCS dpchar dna1[1000+10];char dna2[1000+10];int len1 , len2;int dp[1000+10][1000+10];//表示dna1 从第1位到i 和 dna2 从第一位到j的 相似度void init(){    cin>>dna1;    cin>>dna2;    len1 = strlen(dna1);    len2 = strlen(dna2);}int build(){    memset(dp,0,sizeof(dp));    for (int i = 1; i <= len1; ++i){        for (int j= 1; j <= len2; ++j){            bool ok = (dna1[i-1]==dna2[j-1]);            dp[i][j]= max(                dp[i-1][j-1] + ok,                max(                dp[i-1][j],                dp[i][j-1]                )                );        }    }    return dp[len1][len2];}int main(int argc, char const *argv[]){    init();    cout<
        
         <