esc to dismiss

动态规划

[知乎:什么是动态规划(Dynamic Programming)?动态规划的意义是什么?] https://www.zhihu.com/question/23995189

四大常用算法:分治、回溯、贪心 和动态规划(简称动规)

动态规划(Dynamic programming,简称DP)是一种将复杂问题分解成相对简单的子问题的方法。

术语(摘自百度百科,做了些改动):

  • 多阶段决策问题:如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。

  • 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同。

  • 状态:状态就是事物在特定时间内的特定条件,比如下面的“打家劫舍”题目中我们定义 状态变量 f(n) 为第n阶段打劫到的最大金钱数。

  • 无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。

  • 决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

  • 策略:由每个阶段的决策组成的序列称为策略。达到最优效果的策略称为最优策略

  • 状态转移方程:给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程。

  • 最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略” 。最优性原理实际上是要求问题的最优策略的子策略也是最优。

符合动态规划的题目有三个特点:

  1. 最优子结构:问题的最优解包含子问题的最优解,也就是说,可以通过子结构的最优解推导出问题的最优解。

  2. 无后效性:每个阶段的状态不会影响后续阶段。

  3. 重叠子问题:

理解起来有些复杂。

看例子,比如你有不限量的1元、5元、10元、50元、100元面额的钞票,试问如何用最少数量的钞票来买东西。这道题用贪心算法即可完成,先尽量用最大面额的钞票,超过了商品价格再用次小的,依次选择。比如: 71元的物品,选择 50 → 10(*2) → 1, 一共需要4张。

而如果有一个奇怪的国家发行了 1元、5元、11元面额的钞票,那还能用贪心算法吗?看个例子,比如买 15元的东西,那贪心的策略会导致这样的结果: 11 → 1(4), 需要5张,而如果用 5 元 3 只需要 3张,显然贪心算法在这种场景下就失效了,这就要用到动规了。(为什么国家发行的钞票面额都是1、2、5、10... 这种)

再看个LeetCode 上的题目示例,198. 打家劫舍

简单的描述该题,即小偷要偷一些连续的房屋,但不能偷紧邻的房屋,如何偷得最多的钱?

LeetCode 上的图解:

第1步:从第1个房屋开始,可以决策偷或不偷,偷:2,不偷:0,取最大值2

第2步,决策第2家:偷:7,不偷:2(偷第1家),取最大值7

第3步,决策第3家:偷(加上第1步的最大值):11,不偷(第2步的最大值):7,取最大值11

第4步,决策第4家:偷(加上第2步的最大值):10,不偷(第3步的最大值):11,取最大值11

第5步,决策第5家:偷(加上第3步的最大值):12,不偷(第4步的最大值):11,取最大值12

最后便能得出最大值也就是最优结果为 12.

代码如下:

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func rob(nums []int) int {
    size := len(nums)
    dp := make([]int, size, size)

    if size == 0 {
        return 0
    } else if size == 1 {
        return nums[0]
    }

    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < size; i++ {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    }

    return dp[size-1]
}

这里用到了一个数组 dp, 这是在 动态规划中用来存各阶段状态的数组。状态在动态规划里是个名词,一般动态规划的介绍里会提到几个关键要素:状态、状态转移方程:

  • 状态:可以理解为每个阶段的最优解,如上例中的最大金钱数;

  • 状态转移方程,就是如何通过子结构的状态推导出更大结构的状态,即上例中的: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

好,回到零钱那道题,在 LeetCode 上有: 322. 零钱兑换

我们怎么来得到状态和状态转移方程呢?

我们可以这样思考:比如有 1、5、11 三种面额的硬币,要组成 15 元

我们用 f(n) 表示凑n元钱需要的最少硬币数,例如 f(15) 即要凑成15元需的硬币数。

那么如果选择 1 元,那么还要凑 14 元,这个解法就可以分解为凑14元再加1个1元硬币的子结构,因此这个决策的最优值是 f(14) + 1;

如果选择 5 元,那么还要凑 11 元,这个决策的最优值是 f(11) + 1;

如果选择 11 元, 那么还要凑 4 元,这个决策的最优值是 f(4) + 1;

这样我们只需要取上面三个决策的最小值即为最优值: f(15) = min{ f(14) + 1, f(11) + 1, f(4) + 1 } = min { f(14), f(11), f(4) } + 1, 这就是状态转移方程。我们只要取得每个阶段的最少硬币状态,就可以得到答案。我们可以画一张表来表示:

f(0)     0   // 必须要,想想为什么?
f(1)     1
f(2)     2
f(3)     3
f(4)     4
f(5)     1   // min{f(0), f(4)} + 1
f(6)     2
f(7)     3
f(8)     4
f(9)     5
f(10)    2
f(11)    1   // min{f(0), f(6), f(10)} + 1
f(12)    2
f(13)    3
f(14)    4
f(15)    3

我们可以根据状态转移方程写出代码:

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1, amount+1)
    dp[0] = 0

    for i := 1; i <= amount; i++ {
        best := -1
        for _, c := range coins {
            if i >= c && dp[i-c] >= 0 {
                best = min(best, dp[i-c] + 1)
            }
        }
        dp[i] = best
    }
    return dp[amount]
}

func min(best, val int) int {
    if best >= 0 && best < val {
        return best
    }
    return val
}

再难一点的题: 1043. 分隔数组以得到最大和

更难一点的题:416. 分割等和子集

如何向4岁的小孩解释动态规划?

quora问题:How should I explain dynamic programming to a 4-year-old? Jonathan Paulson 的答案

在白纸上写上 "1+1+1+1+1+1+1+1",问小孩等于几。

小孩数了下答:“8”。

再追加上 "+1",问等于几。

小孩很快答道:“9”。

“你怎么这么快就得到答案了?”

“因为刚才是8,再加1得9。”

“对了,这就是动态规划。”

名言

那些不牢记过去的人,注定要重复过去发生的事。 —— 乔治·桑塔亚那 (西班牙裔美国哲学家)

Those who cannot remember the past are condemned to repeatit. by George Santayana

参考资料:

Dynamic Programming - Part 1: https://techparoksha.quora.com/Dynamic-Programming-Part-1

x