进一步理解动态规划

在理解动态规划、BFS和DFS一文中，只是初步讲解了一下动态规划，理解的并不到位，这里再加深理解一下。

本文主要参考什么是动态规划一文。

一、前言

1.1、算法问题的求解过程

类似于机器学习的步骤，对同一个问题，可以用不同的模型建模，然后对于确定的模型，可以用不同的算法求解。

一般的算法问题求解步骤，分为两步：

  • 1、问题建模：
    对于同一个问题，可以有不同的模型。
  • 2、问题求解：
    对于特定的模型，选出一个合适的算法（时间复杂度和空间复杂度满足要求），求解问题。

对应到动态规划算法上，具体分为这两步：

  • 1、问题建模：[最优子结构]，[边界]，[状态转移方程]。
  • 2、用动态规划算法求解问题。

1.2、动态规划的思想

大事化小，小事化了。把一个复杂的问题分阶段进行简化，逐步化简成简单的问题。

1.3、动态规划的步骤

1.3.1 问题建模
  • 1、 根据问题，找到【最优子结构】。
    把原问题从大化小的第一步，找到比当前问题要小一号的最好的结果，而一般情况下当前问题可以由最优子结构进行表示。
  • 2、确定问题的【边界】。
    根据上述的最优子结构，一步一步从大化小，最终可以得到最小的，可以一眼看出答案的最优子结构，也就是边界。
  • 3、通过上述两步，通过分析最优子结构与最终问题之间的关系，我们可以得到【状态转移方程】。
1.3.2 问题求解的各个方法（从暴力枚举 逐步优化到动归）

  • 暴力枚举：
    下面的楼梯问题，国王与金矿问题，还有最少找零硬币数问题，都可以通过多层嵌套循环遍历所有的可能，将符合条件的个数统计起来。只是时间复杂度是指数级的，所以一般 不推荐。

  • 递归：
    1、既然是从大到小，不断调用状态转移方程，那么就可以用递归。
    2、递归的时间复杂度是由阶梯数和最优子结构的个数决定的。不同的问题，用递归的话可能效果会大不相同。
    3、在阶梯问题，最少找零问题中，递归的时间复杂度和空间复杂度都比动归方法的差， 但是在国王与金矿的问题中，递归的时间复杂度和空间复杂度都比动归方法好。这是需要注意的。

每一种算法都没有绝对的好与坏，关键看应用场景。、

上面这句话说的很好，不止于递归和动归，一般的算法也是，比如一般的排序算法，在不同的场景中，效果也大不相同。

  • 备忘录算法：
    1、在阶梯数N比较多的时候，递归算法的缺点就显露出来了：时间复杂度很高。如果画出递归图（像二叉树一样），会发现有很多很多重复的节点。然而传统的递归算法并不能识别节点是不是重复的，只要不到终止条件，它就会一直递归下去。
    2、为了避免上述情况，使递归算法能够不重复递归，就把已经得到的节点都存起来，下次再遇到的时候，直接用存起来的结果就行了。这就是备忘录算法。
    3、备忘录算法的时间复杂度和空间复杂度都得到了简化。

  • 正经的动归算法：
    1、上述的备忘录算法，尽管已经不错了，但是依然还是从最大的问题，遍历得到所有的最小子问题，空间复杂度是O(N)。
    2、为了再次缩小空间复杂度，我们可以自底向上的构造递归问题，通过分析最优子结构与最终问题之间的关系，我们可以得到【状态转移方程】。
    然后从最小的问题不断往上迭代，即使一直到最大的原问题，也是只依赖于前面的几个最优子结构。这样，空间复杂度就大大简化。也就得到了正经的动归算法。

下面通过几个例题，来具体了解动归问题。

二、例题

例1：Climbing Stairs

leetcode原题：你正在爬一个有n个台阶的楼梯，每次只能上 1个 或者 2个台阶，那么到达顶端共有多少种不同的方法？

1.1、 建立模型：

  • 最终问题F(N)：
    假设从0到达第N个台阶的方法共有F(N)个。
  • 最优子结构F(N-1)，F(N-2)：
    到达N个台阶，有两种可能，第一种可能是从第 N-1 个台阶上1个台阶到达终点，第二种可能是从第 N-2 个台阶上2个台阶到达终点。
  • 最优子结构与最终问题之间的关系：
    按照上述表达，那么可以归纳出F(N) = F(N-1) + F(N-2) (n>=3)

结束条件为F(1) = 1,F(2) = 2

1.2、 问题求解：

1.2.1、 解法1：递归

先用比较容易理解的递归求解（结束条件已知，递归公式已知，可以直接写代码了）

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

回想前面所说，递归的时间复杂度是由阶梯数和最优子结构的个数决定的。这里的阶梯数是 N ，最优子结构个数是 2 。如果想象成一个二叉树，那么就可以认为是一个高度为N-1，节点个数接近 2 的 N-1 次方的树，因此此方法的时间复杂度可以近似的看作是O(2N) 。

1.2.2、 解法2：备忘录算法

参考什么是动态规划中递归的图，发现有很多相同的参数被重复计算，重复的太多了。

所以这里我们想到了把重复的参数存储起来，下次递归遇到时就直接返回该参数的结果，也就是备忘录算法了，这里需要用到一个哈希表，解决方法就是对类用init进行初始化。

class Solution:
    def __init__(self):
        self.map = {}
        
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n in self.map:
            return self.map[n]
        else:
            value  =  self.climbStairs(n-1) + self.climbStairs(n-2)
            self.map[n] = value
            return value

这里哈希表里存了 N-2 个结果，时间复杂度和空间复杂度都是O(N)。程序性能得到了明显优化。

1.2.3、 解法3：动态规划

之前都是自顶向下的求解，考虑一下自底向上的求解过程。从F(1)和F(2)边界条件求，可知F(3) = F(1)+F(2)。不断向上，可知F(N)只依赖于前两个状态F(N-1)和F(N-2)。于是我们只需要保留前两个状态，就可以求得F(N)。相比于备忘录算法，我们再一次简化了空间复杂度。

这就是动态规划了。（具体的细节看漫画比较好理解。）

具体代码实现中，可以令F(N-2)=a，F(N-1)=b，则temp等于a+b，然后把a向前挪一步等于b，b向前挪一步等于temp。那么下一次迭代时，temp就依然等于a+b。

代码如下：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        a = 1
        b = 2
        for i in range(3,n+1):
            temp = a + b
            a = b
            b = temp
        return temp

例2： Making change using the fewest coins.

参考Dynamic Programming中，用最少的硬币数目找零钱的一个例子。

问题描述：
假设你是一家自动售货机制造商的程序员。你的公司正设法在每一笔交易 找零时都能提供最少数目的硬币以便工作能更加简单。已知硬币有四种（1美分，5美分，10美分，25美分）。假设一个顾客投了1美元来购买37美分的物品 ，你用来找零的硬币的最小数量是多少？
（这个问题用贪心算法也能解，具体细节看参考文献）

2.1、 建立模型：

就以动归作为解题的算法来建立模型吧。

  • 边界：当需要找零的面额正好等于上述的四种整额硬币时，返回1即可
  • 最优子结构：回想找到最优子结构的方法，就是往后退一步，能够得到的最好的结果。这里有四个选择，1 + mincoins(63-1)，1 + mincoins(63-5)，1 + mincoins(63-10) 或者 1 + mincoins(63-25)，这四个选择可以认为是63的最优子结构。
  • 状态转移方程：按照 上述的最优子结构，mincoins(63)也就等于上述四个最优子结构的最小值。于是，方程可以表示为：

2.2、 问题求解：

模型已经得到，接下来就运用算法进行求解。
这里依然可以按照例1的解法，由模型，很自然的想到用递归求解。

2.2.1、解法1，递归

边界条件已知，模型已知，可以直接写代码了。

def recMC(coinValueList,change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList,change-i)
        if numCoins < minCoins:
            minCoins = numCoins
    return minCoins
print(recMC([1,5,10,25],63)

但是，对于每一个大于25的数目，都有四个最优子结构，然后对于每个最优子结构，还有大量相同重复的参数（具体细节看参考）。所以这个解法并不合适。

2.2.2、解法2，动态规划

首先要有自底向上的思想，从change等于1时，开始往上迭代，参考最优子结构，记录下来最少硬币数。一直迭代到63。

1==>1
2==>min(2-1) + 1 = 2
3==>min(3-1) + 1 = 3
4==>min(4-1) + 1 = 4
5==>min（min(5-1) + 1 = 5， min(5-5) + 1 = 1）= 1
6==>min（min(6-1) + 1 = 2， min(6-5) + 1 = 2）= 2
7==>min（min(7-1) + 1 = 3， min(7-5) + 1 = 3）= 3

由此可以推下去，每一个change对应的最少硬币数，都可以由前面的若干个最优子结构（有几个最优子结构，由change是多少决定，change大于5就有两个子结构，大于10就有三个。。）得到。这样一直迭代到63，那么就可以得到63的最少硬币数。

因此，需要一个循环来从头到尾遍历。
需要一定需要一个map来记录部分结果。
每一个change，我们可以根据上面的式子遍历最优子结构，并将每个子结构的结果都添加到一个list中，在遍历完最有子结构以后，选择最小的那一个，添加到map中去。

求解一个新的 i 的最优解的过程是很方便的，从最优子结构中挑选最小的值然后加1即可。
最优子结构的值，可以用minCoin[i-j]得到。其中j为有效硬币面额。

实现代码：

def dpMakeChange(coinValueList,change):
    minCoins = { }

    for cents in range(change+1):
        #cents小于等于1时，coinCount会为空，没法执行min。
        #因此这里先填上
        if cents <= 1:
            minCoins[cents] = cents
            continue
        #遍历cents的每个最优子结构并且添加到list中，等待筛选
        coinCount = [ ]
        for j in coinValueList:
            if cents >= j:
                coinCount.append(minCoins[cents - j] + 1)
        minCoins[cents] = min(coinCount)
    return minCoins[change]

result = dpMakeChange([1,5,10,25],63)
print(result)

当然这个函数是有瑕疵的，因为这个函数只告诉我们最少的硬币数，并不能告诉我们应该找零的面额。所以我们可以扩展一下函数，跟踪记录我们使用的硬币即可。具体细节可以看参考。

例3： 国王与金矿问题

只讲一下大致的思路。
问题中需要注意的地方：

  • 国王与金矿的问题中，因为每个金矿需要的人不同，所含金矿数量也不同。为了简化问题，这里第 i 个金矿所含的金矿数量和所需要的工人都是 特定不变的。
  • 在实现自底向上的递推时，因为问题的参数有两个，那么存在两个输入维度。为此，可以画一个表格来做分析。
  • 在实现自底向上的递推时，为了比较快的找到规律，最好把从边界不断地往上迭代，结合最优子结构和存储的结果，慢慢的找到规律。

3.1、问题建模

这里着重讲解一下最后一点，也就是动态规划最重要的地方。

最优子结构：对于5个金矿，10个工人的情况，往后退一步存在两种情况。（第五个金矿的金矿数量为350，所需工人为3人）

  • 情况1：国王选择不挖第五个金矿，那么此时最大化的金矿数量就是在有4个金矿，10个工人的情况下，能够挖到的最多金矿数量。
  • 情况2：国王选择挖第五个金矿，那么此时用3个工人挖得350的金矿数量是已知的，还剩4个金矿与7个工人。
    那么最优解相当于在4个金矿与7个工人的情况下能够挖得的最多金矿数量 + 350。

最优子结构与最终问题之间的关系：5个金矿10个工人的最优选择，就是上述两个最优子结构的最大值。

于是我们可以得到状态转移方程：

最重要的状态转移方程已经得到，至于剩下的边界条件，现实中会遇到的各种特殊情况，这里就不赘述了。细节参考漫画。

3.2、问题求解

3.2.1 解法1、递归

程序 ：把状态转移方程翻译成递归程序，递归的结束条件就是方程式中的边界即可。
复杂度：因为每个状态有两个最优子结构，所以递归的执行流程类似于一个高度为N的二叉树。所以方法的时间复杂度是O(2N)。

3.2.2 解法2、备忘录算法

程序：在简单递归的基础上，增加一个HashMap备忘录，用来存储中间的结果，HashMap的Key是一个包含金矿数N和工人数W的对象，Value是最优选择获得的黄金数。
复杂度：时间复杂度和空间复杂度相同，都等于被网络中不同Key的数量。

3.2.3 解法3、动态规划

为了实现自底向上的迭代，对于参数有两个的问题，我们可以先画要一个表格来做分析。根据状态转移方程，我们可以方便的画出表格。注意，一定是要根据状态转移方程来求的。

由于我们在求解每个格子的数值时，结合状态转移方程，发现除了第一行以外，每一个格子都可以由前一行的格子中的一个或者两个格子推导而来。
从整体上来说，每一行的值都可以由前一行来求得。

于是，我们在写代码的时候，也可以像画表格一样，从左至右，从上到下一个一个的推出最终结果。反映到程序上就是：

for i in range(金矿数):
    for j in range(工人数目):
         状态转移方程

另外，由上可知，我们并不需要存储整个表格，只需要存储前一行的结果即可推出新的一行。

代码这里就不写了。

注意：

  • 这里动态规划的时间复杂度是O(n*w)，空间复杂度是O(w)。在n=5，w=1000是，显然要计算5000次，开辟1000单位的空间。
  • 但是如果用简单递归算法的话，时间复杂度是O(2N)，需要计算32次 ，开辟5单位（递归深度）的空间。
  • 这是由于动态规划方法的时间和空间都和w成正比，而简单递归却和w无关，所以当工人数量很多的时候，动态规划反而不如递归。

所以说，每一种算法没有绝对的好与坏，关键要看应用场景。

总结：

个人觉得， 动态规划算法最重要的有两点

  • 建模：一定要找对最优子结构，然后分析最优子结构与最终问题的关系，从而得到状态转移方程。
  • 问题求解：先手动的自底向上的，运用状态转移方程迭代一下，一直到最终问题，从而确定程序的主体部分。

至于，模型中的边界问题，特殊情况等，就是需要多敲代码来慢慢考虑的了。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,324评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,303评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,192评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,555评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,569评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,566评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,927评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,583评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,827评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,365评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,941评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2赞 342

推荐阅读更多精彩内容