动态规划算法,3000字真正帮助你入门
共 3762字,需浏览 8分钟
·
2021-01-27 19:40
读者朋友们好,我是 zhenguo
今天这篇文章我构思很久,也写了很久,全文3330字,21张图。如果可以的话,希望文末能点赞支持下,谢谢。
本文目标帮助朋友们认识到动态规划算法之美,从而引发学习它、研究它的兴趣。
一 动态规划引言
某个问题一旦找到动态规划的解法,一般便是接近或就是最优解法,也正因为此,无数程序员为它着迷,大厂面试也是必考。
但是,动态规划又非常灵活,本质上没有套路,问题不同,动态规划的迭代方程就不同。而有些问题,对于计算机科学家,都难以找到迭代方程。因此,对于平平常常的我们,刷算法题时想不出动态规划的解法,也大可不必气馁。
虽然它很难,但却对训练我们的算法思维,很有帮助!并且持续的练习、总结,也会为我们日后做程序优化、性能提升、算法优化相关工作,打下最为坚实的基础。
一成不变、日复一日的重复,难免让人感到厌烦,如果添加一些灵活多变的成分,生活便会变得有意思起来。不断追寻、不断靠近目标的日子,才更有意义!
二 穷举解法
下面结合一道经典的题目:最大子数组的和,对比暴力枚举解法和动态规划解法,进而体会动态规划的魅力。
给定一个整数数组 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 algorithm,Kadane算法使用的决策策略,非常巧妙,非常简洁:
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
基于本文的讲解,再去看看这道题目,或许思路会豁然开朗。
以上就是动态规划的入门解读,我已经将此文整理为PDF,需要PDF的微信我,备注:动规
算法刷题日记
作者:zhenguo
这是我的另外一个公众号:算法刷题日记,我正在努力打造它为精品公众号,只做算法刷题的推文推荐,目前已原创 60 多篇算法刷题的精品解读。