理解动态规划

1,936

动态规划是一个经典而实用的算法,经常在面试题中出现。

以最著名的刷题网站leetcode为例,目前有147道动态规划算法题,占比约 13% 。

其重要性可见一斑~

这篇文章就来详细分析一下动态规划相关知识点。

定义

综合维基百科和《算法导论》的说法,能使用动态规划解决的问题必须包含下面两个要素:

  1. 重叠子问题。
  2. 最优子结构。

重叠子问题很好理解,递归就是解决重叠子问题的一种方式。 简单理解就是父问题和子问题处理方式一致,但是规模不同。 下面来重点需要分析最优优子结构。

最优子结构

什么是最优子结构?

问题的最优解包含其子问题的最优解。

或者说就是通过子问题的解可以推导出父问题的解。记住是子问题的解而不是子问题本身。

如何理解?举个例子:

给定一个整数数列 [12, 18, 21, 60],求下面两个问题

  1. 偶数个数。
  2. 最小公倍数。

对于第一个问题就是具有最优子结构,因为将问题(数组)拆分后求解的结果可以用于问题本身的解。

子数组的偶数个数 + 当前数是否为偶数 ? 1 : 0 = 数组的偶数个数

第二个问题就不具有最优子结构,将问题(数组)拆分后求得的解不能直接用于问题本身的解。

子数组的最小公倍数 + 数组某个元素 =/=> 当前数组最小公倍数

第一个问题我们不需要关心子数组的内容,只需要关心子数组的结果即可,而第二个问题我们需要知道子数组的组成。

当然有专业术语可以来表述这种情形,叫做“无后效性”。

如何找到最优子结构?

《算法导论》中给出的通用模式(套路)如下:

  1. 将问题进行拆分,通常会拆分成多个待求解的子问题。
  2. 假定已经知道了子问题的最优解。
  3. 给定最优解选择后,确定会产生哪些子问题,对子问题空间进行刻画。
  4. 证明子问题的解是原问题最优解的组成部分。

虽然我对描述语言进行了精简,但是看起来还是有些啰嗦。再用一句话来概括就是“不断缩减问题的规模”,记住是缩减规模不是缩减条件。

以爬楼梯问题为例进行说明:

题目:一个人上楼梯,楼梯有n阶台阶,一次可以上1阶或2阶。问有多少种上楼梯的方式。

对于这个问题使用动态规划来考虑,分解的子问题应该是:

爬 n - 1 阶楼梯有多少种方式
爬 n - 2 阶楼梯有多少种方式

而缩减条件的方式是(这是错误的思路)

爬 n 阶楼梯每次只爬1阶有多少种方式
爬 n 阶楼梯每次只爬2阶有多少种方式

优势

理论上来说,大多数问题都可以通过(暴力)枚举来解决。但是通常枚举是下册,因为效率太低,无法在有限的时间或空间内得到结果。

所以我们如果将动态规划算法和枚举相比,那么它至少具有两个优势。

  • 筛选。父问题一定是从子问题的最优解得到,也就是说子问题的非最优解是不会被考虑和计算的。
  • 缓存。子问题的最优解会被记录下来,用于推导父问题的最优解,从而避免重复计算。

例子

借用知乎答主阮行止的一个例子进行说明。

题目:一个国家的钞票面额分别是1元、5元、11元,如何用最少的钞票凑出15元?

先看解答过程:

dp(n)函数表示凑出n元时需要的钞票数量。 那么n = 15时考虑可能由 n=10 时加一张5元,n=14 时加一张1元,n=4 时加一张11元。用公式表述如下:

dp(15) = min{dp(10) + 1, dp(14) + 1, dp(4) + 1}

加上已知条件:dp(11) = dp(5) = dp(1) = 1,整个推导公式如下图:

{% asset_img dp15.jpg %}

然后再结合起来理解动态规划算法的优势。

  • 筛选。例如 dp(15) = dp(5) + dp(5) + dp(1) + dp(1) + dp(1) + dp(1) + dp(1) 这种解显示是不会被计算的,因为它不是某个子问题的最优子结构。这样的好处是避免了无效计算。
  • 缓存。例如 dp(3) = dp(2) + 1 = [dp(1) + 1] + 1 这个子问题的最优解会被重复用到,所以可以用数组来缓存子问题的最优解,从而避免了重复计算。

思考题

某公司出售一段长度为99米可切割的钢条,已知钢条的价格为Pi(i=1,2,3...),钢条长度均为整数。长度价格关系如下:

长度i    1    2    3    4    5    6    7    8    9    10
价格Pi   1    5    8    5    10   17   17   20   24   30

求收益最大的切割方案。


参考:


原文链接:tech.gtxlab.com/dp.html 作者信息:朱德龙,人和未来高级前端工程师。