加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 站长学院 > PHP教程 > 正文

HDU 1159——Common Subsequence

发布时间:2020-12-13 21:57:30 所属栏目:PHP教程 来源:网络整理
导读:链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159 ? 题解 #includeiostream #include cstring using namespace std; char A[ 1005 ],B[ 1005 ]; // 存放字符串 int dp[ 1005 ][ 1005 ]; // 存放到字符串a第 i+1个字符,字符串b第 j+1个字符为止的最大长

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159

?

题解

#include<iostream>
#include<cstring>
using namespace std;
 
char A[1005],B[1005]; //存放字符串 
int dp[1005][1005]; //存放到字符串a第 i+1个字符,字符串b第 j+1个字符为止的最大长度公共子序列的长度
 
int main(){
    while(~scanf("%s%s",A,B)){
        int alen=strlen(A),blen=strlen(B); //注意头文件
        for(int i=0;i<alen;i++){
            for(int j=0;j<blen;j++){
                if(A[i]==B[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
        printf("%dn",dp[alen][blen]);
    }
    return 0;
}

?

定义 dp[ i ][ j ]为 A1...Ai 和 B1...Bj 对应的 LCS(最长公共子序列)长度

那么,A1...Ai+1 和 B1...Bj+1 对应的公共子列可能是

  • 当?Ai+1==Bj+1时,在 A1...Ai 和 B1...Bj 的公共子列末尾追加上 Ai+1
  • A1...Ai+1 和 B1...Bj 的公共子列
  • A1...Ai 和 B1...Bj+1 的公共子列

三者中的一个,则有以下递推关系成立

?

该递推式时间复杂度O(nm),dp[n][m]就是LCS的长度

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读