题目 2086: [蓝桥杯][算法提高VIP]最长公共子序列（dp动态规划Python)代码及注释

深碍√TFBOYSˉ_ 2022-12-21 02:25 9阅读 0赞

# 题目 #

> 题目描述  
> 给定两个字符串，寻找这两个字串之间的最长公共子序列。  
> 输入  
> 输入两行，分别包含一个字符串，仅含有小写字母。  
> 输出  
> 最长公共子序列的长度。  
> 样例输入  
> abcdgh  
> aedfhb  
> 样例输出  
> 3

分析题目：这是经典动态规划题目，通过读题确定状态矩阵dp为二阶矩阵（**因为是在两个字符串间进行比较，一维矩阵不足以支持记录状态**）。  
**dp\[i\]\[j\]表示第一个字符串a的前（i+1)个字符与第二个字符串b的前（j+1)个字符的最长公共子序列。**  
确定状态转移方程为:  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhcnJ5X19fX19f_size_16_color_FFFFFF_t_70_pic_center][]

# Python代码 #

'''
    主页有：
          ①2011——2018蓝桥杯真题以及第十届蓝桥杯大赛决赛真题。
            蓝桥杯VIP题目提交渠道，超详细截图教程。
          ②蓝桥杯题库赛题Python代码解析
          ③python版的数据结构和算法，并且配备各阶段的例题，适合新手入门看。
        欢迎关注=.=，如果这个博客对你有帮助的话可以点个赞，有问题
        或者别的意见可以在评论下方提出，我看到会及时回复，谢谢~
    
        另外，刚刚上手Python的同学可以参考菜鸟教程学习：
        https://www.runoob.com/python3.html
    '''
    a=list(str(input()))
    b=list(str(input()))
    dp=[[0]*len(b) for i in range(len(a))]#初始化二阶状态矩阵
    #dp过程
    for i in range(0,len(a)):
        for j in range(0,len(b)):
            if (i==0 or j==0) and a[i]==b[j]:
                dp[i][j]=1
            if i>0 and j>0 and a[i]==b[j]:
                dp[i][j]=dp[i-1][j-1]+1
            if i>0 and j>0 and a[i]!=b[j]:
                dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
    
    print(dp[-1][-1])

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhcnJ5X19fX19f_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/322552f323a144dcb4682157740a61c0.png