我的第437篇原创：动态规划算法入门篇，真正帮助你入门！！！

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，就题目中给定的数组：[-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 多篇算法刷题的精品解读。