0%

动态规划

动态规划一直以来,算是一个弱点,前几腾讯的实习生笔试有道区间DP的题目,当时只能暴力的使用了递归,存在大量的重复计算,时间复杂度会达到O(N^2)。所以今日,查资料,从基础学习DP。

首先参考的资料是知乎回答:什么是动态规划?动态规划的意义是什么? 。王勐和徐凯强帮我建立的对DP的概念认识和理论认知,在这点上,两位的答案要比书中讲解的好,因为更直白。

之后,扔掉他们两个的回答,对最长递增子数列(LIS),自己分析,写状态定义,写转义方程,写代码实现。当然在实现中还是踩了很多坑,比如数组的初始化值。

后续完成了LeetCode OJ上以前遇到过的DP题目,帖到GIST动态规划合集。后面做的动态规划题目,也会继续贴到这个GIST上。

看了知乎的回答,并不能让人掌握DP,只能在你了解DP的时候,帮助你梳理自己对DP的理解。

因此,总觉的内心空空的,把握不住DP,下载了刘汝佳的《算法竞赛入门经典》(简称算法入门)又找到一本《算法设计和分析基础(第三版)》(简称算法设计基础),算法设计基础的动态规划比第二版的要好,作者说更简单,有种由浅入深的感觉。当看到第一个例子是斐波那契数列的时候,我就感觉,例子是不是太简单了,转而去看算法入门。

虽然算法入门已经被黑出翔了,当对我而言,这本书还是有很大帮助的,数字三角形的问题很基础也简单易懂,也讲解了递归,记忆化搜索,等一些技巧,对,按前面知乎提到的,这只是技巧。在看DAG和最长路、最短路的时候,了解了边界情况,初试值的设定,提高阅读性的技巧。然而这已经耗尽了一上午、一下午加部分晚上的时间。晚上跳过了两个小节,去看了一下9.4经典模型,这个时候,已经能尝试着去自己定义状态和转义方程。

再次回到《算法设计和分析基础》,8.1节比斐波那契数列深入了一些,我研究了每个例子的状态和他们的转移方程,列出边界,并且动手去模拟算法,之后去做8.1节的习题,这些题目是例子的变形,很庆幸,自己能写出结果来,确实是由浅入深。

随着我对DP的基类,我对简单的DP有些许自信了,并且应该做出下面的总结,即便,在将来看来是错误的:

  1. DP是一种思想,将问题分解为子问题,子问题之间存在依赖性。
  2. DP的核心是定义状态和转移方程。仔细思考如何定义状态:比如是从i开始的结果(数字三角形),还是以i结束的结果(Coin-row,Change-making,Coin-collecting)。
  3. 清楚当前问题的边界。
  4. 写出尽量完备的测试例子。
  5. DP的题目大多是最优解的考察,如果是最大、最长等问题我一般会先写出F[i] = max{___},然后向里面去填空。
  6. 去实现DP的时候,函数不应该太大。不然,很可能你已经写错代码了,就像机器学习中的过度拟合一样。
  7. DP有两个提到的是自上而下(top-down)的DP,上推(bottom-up)的DP,当然还有其他版本的DP。
  8. DP的效率并不一定比分治、贪心快,比如LIS。
  9. 如果终点时固定的,状态的定义往往是从起点,到当前位置,所得到的结果。

以下更新于2016年4月5日。

既然DP的核心是状态的定义和转移方程,定义状态的基础是确定自变量和因变量,因变量就是题目要求的最优解,而自变量就需要根据题意设定了,在确定题目之后,一般就能发现与因变量相关的一些变量,并不能拿这些变量全部作为自变量,应当探索着取其中的一个作为自变量,如果不行,再取两个。

这面罗列一些,白天总结的自变量和因变量。

Coin-row

一行硬币,取若干硬币,使得硬币的和最大,取出的硬币不相邻。

  • 因变量:取出的硬币的和。
  • 自变量:通常来讲是硬币的数量和币值,但这里是已经固定的硬币的排列,并且是最优化问题,最大的和,这里把自变量n定义为前n个硬币。
  • 再完善因变量:满足取出条件的最大和。
  • F(k):前n个硬币,满足不相邻条件,所能得到的最大和。
  • 结果:max{F(k)| 1 <= k <= n}

Change-making

d[m]为币值,给你一个金额amount,使用最少(多)数量的硬币组成amount。

  • 因变量:硬币的数量。
  • 自变量:因变量同时受币值和amount的影响,这里定义amount为自变量,因为不同的amount之间,可以通过d[i]转移。把amount和d[i]换为另外一个amount问题,比如,amount为10块钱,d[i]为5块的币值,那么就可以把F(10)和F(5)关联起来,由于还存在其他币值,可以把F(10)与所有的F(10-d[i])关联起来,选取期中的最优解。这是终点固定的问题:从节点0出发,到终点amount的最短路径
  • F(k):当前amount所需要的最少的硬币数量。
  • 结果:F(n)

数字三角形问题

数字三角形问题。有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来。求最大和。

  • 因变量:路径上的最大和。
  • 自变量:这是一个二维的,所以自变量为(i,j),起点固定。
  • F(i, j):自(i,j)开始,能得到的最大和,包括(i,j)本身。
  • 结果:F(1,1)

LIS

  • 因变量:
  • 自变量:

背包问题

一个容量为W的包,一堆重量分别为w1…wn,价值分别为vi…vn的钻石,问如何用包装下尽量多的钻石,让总价值最大。

  • 因变量:被选出来的钻石的总价值。
  • 自变量:因变量受W的限制,以及每颗钻石的重量。借鉴change-making的思路,把W设为自变量,将F(W)定义为能钻石的总价值,转移方程可以描述为:F(k) = max{ F(k-wj) + vj | j是剩余的钻石 },这样剩余钻石的集合一直在变,关键是它们不一定连在一起,不容易处理。
  • 自变量再尝试:转换为DAG问题,我们固定一个起点,定义F(k)为前k个钻石,在W的限制下能获得的最大总价值,其实这是有缺陷的,比如我要第k+1个,而不要第k个能得到最优的解,此时w(k+1)比w(k)大,但恰好又能装进去,但按照F(k)的定义,我们得不到最优解。这个时候,我们已经离找到正确的定义比较近了。
  • 自变量再尝试:既然因变量还受W的限制,我们把容量也作为一个自变量,设置二元自变量,F(i,j)定义为:前i个元素,在容量限制为j的情况下,所能获得的最大价值。这时候对于i而言,有两种状态,一种是包含了i,一种是没有包含i,若包含了i,F(i,j) = v(i) + F(i-1, j-w(i)),如果没有包含i,则F(i,j) = F(i-1, j)。而F(i,j)是两者之中的最大值,这里面是有边界的,就是如何判断是否包含i,在表达式F(i,j) = v(i) + F(i-1, j-w(i))中,存在j-w(i),这个就是边界,如果j>=w(i),那么可能包含i,反之,一定不包含。
  • 结果:F(n, W)。

更新于:2016年4月6日

一篇对易理解的DP文章:从新手到专家

欢迎关注我的其它发布渠道