DP动态规划———LCS最长公共子序列

浏览数:353

2019-10-7

　　递推公式：

if(a[i-1]==b[j-1])
{
    dp[i][j]=dp[i-1][j-1]+1;
}
else
{
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

　　完整模板代码：

int LCS(string a,string b){
    int i,j,dp[1000][1000];
    for(i=1;i<=a.size();i++){
        for(j=1;j<=b.size();j++){
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[i-1][j-1];
}

作者：dynmi

原文地址：https://www.cnblogs.com/dynmi/p/11310936.html

喜欢 0

DP动态规划———LCS最长公共子序列

相关推荐