动态规划民科教程

这是我本人近段时间学习和练习动态规划的总结,因为本人不是练过ACM的,所以自称民科。文章末尾是一些有用的引用。

动态规划(Dynamic Programming),一听就是一个高大上的词语,我们先来看看维基百科是怎么说的:

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

总结一下,动态规划是:

  • 一类问题的解法的总称,而不是某个具体算法的名称
  • 通过将原问题分解成子问题,并且记忆子问题的解,从而解出原问题

将一个问题分解成子问题,然后解决子问题并且记住结果,从而解决原问题。我们先忽略记住子问题的结果这一部分,这句话就变成了:"将一个问题分解成子问题,然后解决子问题,从而解决原问题。"。是不是感觉似曾相识?在归并排序中,我们就曾经用过这样的手法,先将数组无限划分,一直到只剩下一个元素,然后逐层往上归并。我们就是这样把原问题划分成子问题,然后解决子问题,最后原问题也得以解决的。

而这里,我们用到了一个非常有助于抽象的工具,那就是递归。

递归

确切的来说,只要自身调用自身,就可以称之为递归,但是本文中所说的递归,都是有把问题划分成子问题,然后调用自身的。
比如,打印一个列表,我们可以这样递归的打印:

def print_list(alist):
    if len(alist) == 0:
        return

    print(alist[0])

    print_list(alist[1:])


if __name__ == "__main__":
    print_list([5, 4, 3, 2, 1])

我们先来看看上面的程序是怎么工作的,首先,我们检查基本情况,那就是列表是空的,那么我们无需打印什么,直接退出。否则,我们把列表分割成两份,一个 item,和一个列表,例如 [5, 4, 3, 2, 1] 就可以分割成 5[4, 3, 2, 1],打印5之后,我们再调用当前执行的这个函数自身,并且把 [4, 3, 2, 1] 作为参数,于是最后,就打印出了 5 4 3 2 1。把上面的函数调用
画出来,就是这样:

通过逐次减小问题的规模,最终我们解决了原问题。

暴力递归

接下来我们看另外一个比较经典的问题:斐波那契数列
我们要求斐波那契数列中的第n位。经典的定义是:

fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = (+) (fib $ n - 1) (fib $ n - 2)

我们把计算 fib(5) 的所有计算和递归所产生的子问题画出来:

记忆化

如果仔细观察,我们会发现,上图的fibbnacci其实包含了很多重复计算,如下图所示:

那如果我们通过把已经计算过的结果存储下来,每次计算先检查是否已经计算过,从而消除重复计算,速度会不会快很多呢?答案是会。看下面的跑分:

In [1]: def fib1(n):
   ...:     if n in (1, 2):
   ...:         return 1
   ...:     return fib1(n - 1) + fib1(n - 2)
   ...: 

In [2]: %timeit fib1(20)
1.89 ms ± 39.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [3]: cache = {1: 1, 2: 1}

In [4]: def fib2(n):
   ...:     if n in cache:
   ...:         return cache[n]
   ...:     cache[n] = fib2(n - 1) + fib2(n - 2)
   ...:     return cache[n]
   ...: 

In [5]: %timeit fib2(20)
181 ns ± 4.17 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

1.89ms 大概是 181ns 的10441倍!

告诉你一个不幸的消息,这就是动态规划。没错,就这么简单,这就是动态规划,还记得我们上面说过的吗?定义子问题,我们做到了,fibnacci原生的定义就已经告诉了我们子问题是什么。解决子问题并且记住子问题的解,我们做到了,每次计算出结果后,先存到cache里,然后才返回。最终解决原问题。

嗯,递归,总感觉有点跳,是的,为什么突然原问题就被解决了呢?要理解递归,需要一段时间,也许要仔细的思考。接下来我们看一些真实的例子,让我们的思维从迭代跳到递归。

递归的思考

递归这种技巧非常的巧妙,就好象我们从山顶看到山脚一样的感觉,通常我们称之为 "top-down",自顶向下。我们举几个常见的东西,然后我们用递归的方式把他们分解:

  • 字符串可以看作是左边一个字符,加右边一个字符串,比如 "hello" 可以是 'h' + "ello",而递归下去,"ello" = 'e' + "llo" ...
  • 字符串可以看作是左边的一个字符串,加右边一个字符,比如 "hello" 可以是 "hell" + 'o',而递归下去,"hell" = "hel" + 'l'...
  • 字符串也可以看作是两个字符串拼接而成,通常我们会按照一定比例,比如1:1,那么 "hello" 就可以看作是 "he" + "llo",递归下去,"he" = 'h' + 'e', "llo" = 'l' + "lo"...
  • 链表我们可以看作是一个元素,加一个链表
  • 树我们可以看作是一个顶点,加两棵树
  • 森林我们可以看作是一棵树,加无数棵树
  • ...

解决了子问题,原问题就自然而然的得以解决,这叫递归跳跃。 更多可以参考 C程序设计的抽象思维,这本书很好的介绍了递归,以及我们所需要克服的递归跳跃。

top Created with Sketch.