阅读量

原创教程,严禁转载。引用本文,请署名 Python中文网, http://www.zglg.work


本文目标帮助朋友们认识到动态规划算法之美,从而引发学习它、研究它的兴趣。

一 动态规划引言

某个问题一旦找到动态规划的解法,一般便是接近或就是最优解法,也正因为此,无数程序员为它着迷,大厂面试也是经常考。

但是,动态规划又非常灵活,本质上没有套路,问题不同,动态规划的迭代方程就不同。而有些问题,对于计算机科学家,都难以找到迭代方程。因此,对于平平常常的我们,刷算法题时想不出动态规划的解法,也大可不必气馁。

虽然它很难,但却对训练我们的算法思维,很有帮助!并且持续的练习、总结,也会为我们日后做程序优化、性能提升、算法优化相关工作,打下最为坚实的基础。

一成不变、日复一日的重复,难免让人感到厌烦,如果添加一些灵活多变的成分,生活便会变得有意思起来。不断追寻、不断靠近目标的日子,才更有意义!

二 穷举解法

下面结合一道经典的题目:最大子数组的和,对比暴力枚举解法和动态规划解法,进而体会动态规划的魅力。

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大为 6。

就此题而言,原问题是 [-2,1,-3,4,-1,2,1,-5,4] ,子问题如 [-2],[1,-3],[-2,1,-3],[4,-1,2,-5],相应的最大和为:-2,1,1,4

它们都是可行解,但不是最优解。

一共可能的子序列有:n + n*(n-1) / 2 ,对于数组长度为n的问题,暴力求解的时间复杂度为:O(n^2),即穷举所有子序列,找出最大和。

三 初识动态规划

动态规划的基本思想通俗来说,要想求原问题的最优解,只需要求得子问题的最优解,组合子问题最优解,进而得到原问题的最优解。

某个问题是否能应用动态规划,通常需要满足3个条件:

  1. 最优子结构

  2. 后续状态无关性

  3. 重复子问题

这些太理论了,尤其初次接触动态规划,看到这些会很懵。

接下来,我会通过实例,进一步形象化解释这三个条件。

如果确认问题满足这三个条件后,下一步就是去寻找状态相关的决策或策略,此策略如果能在原问题上求得最优解,必然也能使用此策略,求得子问题的最优解。如果不成立,表明策略是失败的。

下面先来判断,这个问题适不适合动态规划求解。

四 最优子结构

下面是原问题:

为了求得最优解,能不能先求解下面蓝色区域表示的子序列的最优解?

如果蓝色色块的最大和是如下紫色连续区域:

那么,考虑上最后一个色块4后,同时比较:包括-5元素在内的最大和如果大于紫色色块的和,那么最大和包括色块4,否则不会包括色块4,就是原来的紫色色块 :

所以只需求得子问题的最优解后,原问题的最优解便能推导出来,这表明此问题具备最有子结构性质!

五 后续状态无关性

能够应用动态规划算法的另一个前提:后续状态无关性。

这个问题很明显,如下蓝色色块区域,子数组的最大和,与后面的红色色块无关:

因此,子序列的最大和问题,具备后续状态无关性。

六 重复子问题

如下是以-2为根节点的,可能连续搜索子路径:

如下是以1为根节点,可能的连续搜索子路径:

任意选取一条以-2为根的子路径:[-2, 1,-3,4],和以1为根的子路径[1,-3,4],求出子路径[-2, 1,-3,4]的连续最大和,后面又去求解子问题[1,-3,4]的连续最大和。

然而,相对于子问题[-2, 1,-3,4]而言,[1,-3,4]是原来问题的子子问题,没有必要再去求解,因为求解子问题[-2, 1,-3,4]的最优解时,一定会考虑子子序列[1,-3,4],否则求解[-2, 1,-3,4]就是错误的。

综上,使用暴力枚举会对很多重复子问题计算,也就是说这个问题具备重复子问题特性!

七 应用动态规划求解

满足以上三个基本条件后,确定可以使用动态规划,而强大的动态规划,能将以上问题时间复杂度降到 O(n)。

卡内基梅大学一位教授首先提出此动态规划的解法,命名为 Kadane's algorithmKadane算法使用的决策策略,非常巧妙,非常简洁:

current_sum = max(x, x + current_sum)

其中 current_sum 初始值为:负无穷

上面策略表达的含义:

  • 如果 current_sum 小于 0,则更新current_sum 值为当前迭代到的元素值 x

  • 如果 current_sum 不小于 0,则 current_sum 值同时吸纳 x 和上一时步的 current_sum

所以,无论 current_sum 大小,当前迭代到 x 值总是会被吸纳到 current_sum 中,这个策略保证了是连续的子数组。

如果再发挥想象力,把current_sum 定义为最大贡献值,如果上一个迭代步的最大贡献值大于0,就会把它吸纳到当前步的current_sum中。

否则当前步的current_sum值不会吸纳之前迭代步的current_sum,只保留当前元素 x 值。

基于此更新策略,能够求出任意一个状态的current_sum,就题目中给定的数组:[-2,1,-3,4,-1,2,1,-5,4],

初始状态,current_sum = float('-inf')

i = 0, x = -2, current_sum = -2

i = 1, x = 1, current_sum = max(1, 1-2) = 1

i = 2, x = -3, current_sum = max(-3, -3+1) = -2

i = 3, x = 4, current_sum = max(4, 4-2) = 4

i = 4, x = -1, current_sum = max(-1, -1+4) = 3

i = 5, x = 2, current_sum = max(2, 2+3) = 5

i = 6, x = 1, current_sum = max(1, 1+5) = 6

i = 7, x = -5, current_sum = max(-5, -5+6) = 1

i = 8, x = 4, current_sum = max(4, 4+1) = 5

从中选择最大的current_sum,便是原问题的最优解,即为 6

八 代码

弄懂以上分析后,最大子数组的动态规划,代码非常简洁:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum, best_sum = float('-inf'), float('-inf')

        for num in nums:
            current_sum = max(num, num + current_sum)
            best_sum = max(current_sum, best_sum)

        return best_sum

九 后续思考

最大子数组和,上面给出了动态规划的解法,还可以使用递归的解法,时间复杂度也是O(n),但是空间复杂度却为O(logn),所以最大子数组的最好解法还是动态规划。

动态规划还常常使用表格,缓存之前各个状态的解,通过空间换取时间,这个也是动态规划常用的技巧之一,但这却不是动态规划最难构思出来的地方,最难的还是设计每个状态步的决策策略,这才是动规的精髓。

另外,不是所有的问题都有动规的解法,比如目前全世界最难求解的旅行商问题,更复杂的多线路配送问题,都属于NP问题,很难找到动态规划的解法,但是一旦找到动规解法,它会将O(n!)问题降为O(n多项式)问题,收益也是巨大的!

十 二叉树的子树最大和

子数组的最大和问题是一维的,存在通过建立每个状态步的最大收益,然后找出最大收益的动规解法。

那么,二叉树的子树最大和,就是二维的子数组最大和问题,同样可以使用动规解法。

思路与本文一维子数组最大和极为相似,也是建立每个树节点的最大收益,这道题在LeetCode上hard级别。

输入:[-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出:42

基于本文的讲解,再去看看这道题目,或许思路会豁然开朗。