• 找到最长公共子串 “BABC”。

  • 通用算法:
    如果遇到相同值,就在在斜对角的值的基础上+1

    if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
    else:
                    dp[i][j] = 0
     class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

    在这里插入图片描述注意: 这个问题的最终答案并不在最后一个单元格中!对于前面的背包问题,最终答案总是在最后的单元格中。但对于最长公共子串问题,答案为网格中最大的数字——它可能并不位于最后的单元格中。

    在这里插入图片描述

    最长公共子序列

    最长公共子序列(Longest Common Subsequence,简称 LCS)指在两个或多个字符串中,以相同的顺序出现,但不一定连续的字符序列。LCS 可以跳过字符位置,但要保持相对顺序。

    举例,考虑字符串 “ABCD” 和 “ACDF”,它们的最长公共子序列是 “ACD”。在这个子序列中,字符的相对顺序是相同的,但不要求是连续的。

    通用:
    如果字母相同,对角线斜上方+1.
    如果字母不同,选择上方和左上邻居比较大的那个。

    if s1[i - 1] == s2[j - 1]:
    	dp[i][j] = dp[i - 1][j - 1] + 1
    else:
    	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
     class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

    在这里插入图片描述

    小结

    ❑ 需要在给定约束条件下优化某种指标时,动态规划很有用。
    ❑ 问题可分解为离散子问题时,可使用动态规划来解决。
    ❑ 每种动态规划解决方案都涉及网格。
    ❑ 单元格中的值通常就是你要优化的值。
    ❑ 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。
    ❑ 没有放之四海皆准的计算动态规划解决方案的公式。

    data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/2301_80205209/article/details/136026230","extend1":"pc","ab":"new"}">>
    注:本文转载自blog.csdn.net的Ashleyxxihf的文章"https://blog.csdn.net/2301_80205209/article/details/136026230"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
    复制链接

    评论记录:

    未查询到任何数据!