经典算法——动态规划入门实例

发表于 | 分类于

经典算法——动态规划入门实例

[TOC]

神马是动态规划

  • 专业定义：

    动态规划的本质，是对问题状态的定义和状态转移方程的定义。通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

    看完之后或许你一个字也没记住，这都是什么鬼？

    这里写图片描述

  • 关键点

    ok，让我们摒弃这些专业的条条框框，直奔主题。其实动态规划的核心就是拆解子问题——把一个大的问题拆解成逐步逐步的小问题，而这些小问题都可以直接由之前更小的问题得到。那么怎么拆解这些小问题呢？

    靠的就是状态的定义和状态转移方程的定义。

    当然，这样还是很抽象的。不如举个栗子：

    这里写图片描述

求解最长公共子串

  • 神马是最长公共子串？

    假定现在有两个字符串，最长公共子串就是它们之间公有的连续的最长子串，就像下图这样

    这里写图片描述

    橙色部分就是最长的公有子串，记住这里一定要连续。那么问题来了？怎么求出任意两个字符串的最长公有子串呢？看似很简单，不过细思又感觉有点点复杂的感觉。

  • 暴力求解

    简单粗暴的方法——先求出str1的所有子串，然后在求出str2的所有子串，然后再一个个比较，找到相同且最大的那个不就好了。ok，我们先来看看要多少次：

    str1的可能情况：

    1
    n+(n-1)+(n-1)+.......+2+1 = ((n+1)*n)/2

    同理str2也是一样：

    1
    m+(m-1)+(m-1)+.......+2+1 = ((m+1)*m)/2

    然后在通过两个for循环一个一个比较就搞定了嘛；

    1
    2
    3
    for i in range(((n+1)*n)/2):
      for i in range(((m + 1) * m) / 2):
          dosomthing()

    ok，这样不就搞定了，so easy，不过感觉有点细思极恐，这也太暴力了，万一字符串很大，这得算多久呀！心疼计算机3s。正所谓暴力膜法不可取，所以这时候我们的动态规划就登场啦。

  • 最开始我们说过，用动态规划算法时最重要的就是要拆解子问题，那么我们如何将这个问题拆解为更小的子问题呢？根据动态规划的思想，我们首先要分析出如何根据已有的结果算出我们需要的结果，举栗来说：

    这里写图片描述

    假如我们已经求好了截至到str1[i-1]与str2[j-1]处两个字符串的最大公有子串，是否可以帮助我们求出截止到str1[i]与str[j]处两个字符串的最大公有子串呢？思考一下：

    为了方便，我们将截止到（这里的截止到要包含str1[i]与str2[j]）str[i]与str[j]处的最大字符串长度记作lcs(i,j)，假如：str1[i] == str2[j]，那么我们直接在lcs(i-1，j-1)后面加1不就是lcs（i，j）了嘛，如果str1[i] !=str2[j]，最大公有子串到这里就结束了，所以经过这两个点没有最大公有子串，直接记作0就好了。

    用数学公式就是：

    1
    2
    f(m,n)=0        str1[m] != str2[n] ;
    f(m,n)=f(m-1,n-1) + 1      str[m]==str2[n];

    转化为代码就是：

    1
    2
    3
    4
    if str1[i]==str2[j]:
      lcs[i][j] = lcs[i-1][j-1] + 1
    else:
      lcs[i][j] = 0

    用一张图片描述整体流程就是：

    这里写图片描述

    ok，既然弄清楚了计算的流程，就可以写出代码，完整代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def lcs(mes1, mes2):
        if len(mes1) > len(mes2):
            mes1, mes2 = mes2, mes1
        data = [[0 for i in range(len(mes2) + 1)] for i in range(len(mes1) + 1)]
        mes1 = "$" + mes1
        mes2 = "$" + mes2
        max_lenth = 0
        end = 0
        for i in range(1, len(mes1)):
            for j in range(1, len(mes2)):
                if mes1[i] == mes2[j]:
                    data[i][j] = data[i - 1][j - 1] + 1
                    if data[i][j] > max_lenth:
                        max_lenth = data[i][j]
                        end = i
        if max != 0:
            result = mes1[end - max_lenth + 1:end + 1]
            print(result)
    if __name__ == '__main__':
        while True:
            try:
                mes1 = input()
                mes2 = input()
                lcs(mes1, mes2)
            except:
                break

这里申请的二维数组比两个字符串都要大1，原因为我们呢将i，j为0的边都赋值为了0（当然，这里为了方便直接把数组都初始化了为0），有点像为我们的动态规划棋盘撒了半圈水雷一样。参考上面的流程图。这是一道经典的动态规划题目，在华为的笔试题里面曾经出现过，上面代码就是之前根据题目写的，已经通过了测试。原题如下：

这里写图片描述

求解最大公有子序列

  • 神马是最大公有子序列

    乍一看，和最大公共子串就两字之差，其实这两个差的还是挺远的。还是上面那两个字符串：

    这里写图片描述

    橙色部分就是他们的最大公有子序列。和子串最大的区别就是这里的子串可以不用连续了，所以叫最大子序列了。这种算法有什么用呢？

    比如：有次毛概老师让你写一篇5000字的论文，可是要交的前一天晚上你才想起来怎么办？当然是网上随便找一篇，但是你又怕老师发现是抄袭的，所以就会在文章开头改点东西，文章中间改点，文章结尾改点，当你以为万事大吉的时候，如果老师刚好学过这个算法，那么可以通过对比最大子序列找到文章的相似度了，然后就。。。。

  • 暴力求解

    。。。。。。。。。。。。这个子集比之前的高多了，有兴趣朋友可以计算试试。。。。。。。

  • 其实仔细想想，这个和最大子串其实是一样一样的，就是递推公式有一丢丢不同，希望大家稍微思考下，应该很快就写出来了。完整代码如下，建议对比之前代码就会发现差别了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    def lcs(mes1, mes2):
        if len(mes1) > len(mes2):
            mes1, mes2 = mes2, mes1
        data = [[0 for i in range(len(mes2) + 1)] for i in range(len(mes1) + 1)]
        mes1 = "$" + mes1
        mes2 = "$" + mes2
        max_lenth = 0
        end = 0
        for i in range(1, len(mes1)):
            for j in range(1, len(mes2)):
                if mes1[i] == mes2[j]:
                    data[i][j] = data[i - 1][j - 1] + 1
                else:
                    data[i][j] = max(data[i - 1][j], data[i][j - 1])
        i = len(mes1) - 1
        j = len(mes2) - 1
        str = ""
        while i != 0 and j != 0:
            if mes1[i] == mes2[j]:
                str += mes1[i]
                i -= 1
                j -= 1
            else:
                if data[i][j - 1] > data[i - 1][j]:
                    j -= 1
                else:
                    i -= 1
        print(str[::-1])
    if __name__ == "__main__":
      lcs("abcdacgw", "acdacvgwc")

    其实就是拷贝的前面代码，改了几行代码和输出而已。

总结

  • 算法是一门很理论通过也很实践的学问，建议先搞清流程，再写代码加深理解。本人算法菜鸟，如果错误，欢迎一起探讨。共同学习进步。