我的第437篇原创:动态规划算法入门篇,真正帮助你入门!!!

原创
2020/11/21 22:26
阅读数 0
Python与算法社区
437篇原创,干货满满
值得星标


01

02

03


三步加星标







读者朋友们好,我是 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,就题目中给定的