[数据结构与算法]python数据结构之动态规划

🐛今天要给大家介绍的内容是数据结构中一种较为重要的思想：动态规划（dynamic programming），听到这里，可能很多小伙伴会觉得这个词很陌生，觉得这是一种很复杂的思想，学习起来很困难，其实并不是这样，动态规划所讲述的知识与动态与规划并无太大关联。对往期内容感兴趣的小伙伴可以参考下面的文章👇:

• python数据类型: python数据结构之数据类型.
• python的输入输出: python数据结构之输入输出、控制和异常.
• python数据结构之面向对象: python数据结构之面向对象.
• python数据结构之算法分析: python数据结构之算法分析.
• python数据结构之栈、队列和双端队列: python数据结构之栈、队列和双端队列.
• python数据结构之递归: python数据结构之递归.
• python数据结构之搜索: python数据结构之搜索.
• python数据结构之排序: python数据结构之排序.
• python数据结构之树: python数据结构之树.
• python数据结构之匿名函数lambda: 匿名函数lambda.

🌹 当你能够理解并发现一类问题属于动态规划的问题时，你就会发现采用动态规划的思路能够大幅度减少解决问题的复杂度。

1. 动态规划的定义

百度百科的定义：在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。 因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

动态规划问题有以下特点：

1. 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 子问题重叠性质：指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。

2.问题引入

看完上面对于动态规划那么多文字，可能认真看完也不会有深入的了解，我们来举一个形象的例子：

2.1 青蛙跳台阶

剑指offer-10
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

碰到这种问题，大家开始想到的方法可能是枚举的方法，n=1时，有1种；n=2时，11、2是2种；n=3时，111、12、21是3种；n=4时…（在这里把第n阶台阶的走法次数记作dp[n]）
读到这里，我提示大家一下，大家有没有发现，我们在计算n=3时的dp[3]，重新把n=1和n=2的情况又算了一遍，或者说，当n=3时，只有两种情况：

1. 第一种情况：n=1走再2步
2. 第二种情况：n=2走再走1步

所以，我们计算dp[3]时只需要计算dp[2]和dp[1],然后dp[3]=dp[2]+dp[1]，同理，我们可以得到如下递推关系式：
$$dp[n]=dp[n?1]+dp[n?2]$$
我们用了dp这个数组来存储了每次的计算结果，我们再算dp[n]的时候只需要知道dp[n-1]和dp[n-2]即可，不需要再重复计算之前的台阶次数。

看一下这道题的解法：

def numWays(self, n: int) -> int:
        if n<=1:#n=0和1的时候都是1
            return 1
        elif n==2:#n=2的时候都是2
            return 2
        else:#上面两部之所以要写的原因是因为dp[0]和dp[1]是推导成功的两个初始值。
            dp=[0 for i in range(n)]#创建一个长度为n的数组用于存储每次的dp[i]
            dp[0]=1
            dp[1]=2
            i=2
            while i<n:#循环计算每个dp[i]的值
                dp[i]=dp[i-1]+dp[i-2]
                i+=1
            a=int(dp[i-1])
            return a%1000000007#n=44后超出数据类型，数据会出错。

看一下运行结果：

我们来总结一下：

• 观察问题是否可以由前面的阶段推导出后面阶段的关系式，因为这样会节省大量重复的计算步骤。
• 定义一个数组或者序列来存储每个阶段需要存储的值，比如我们采用$dp[i]$来存储第i阶楼梯会有多少种方式，这很重要，因为我们需要明确我们递推的最小单元是什么。
• 确定递推公式的初始值是什么，正如青蛙上台阶案例所说的，我们的初始值是$dp[0]$和$dp[1]$,分别代表着上1阶台阶和上2阶台阶的方法数。（0阶台阶的方法数不是第一个元素）

2.2 买卖股票挣钱最多

让我们再来看一道题：

leetcode-121:
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

例如：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

我们来分析一下，这道题利用双循环即可解决，第一个循环用来表示当前股票的价格i，第二个循环用来记录在当前股票价格为i下，后面的天卖出股票能获得的最大利润，这样的话时间复杂度为$O(n^2)$

动态规划思想：我们将这个问题换个角度思考

• 旧：我们前面利用双循环的含义是在当天的价格下买入，后面的天卖出所能获取的最大利润为多少？
• 新：当时间来到第i天，能挣的最大利润为多少？（这里指的第i天的最大利润，不是指在第i天卖出，是到第i天为止，所能卖出的最大利润）

以新的想法，我们就需要知道在第i天卖出股票时，和第i-1天卖出的股票最大利润相比哪个时间挣得多？声明dp[i]为在第i天时，股票所能获取的最大利润，那么我们就会出现如下表达式：
$$dp[i]=max(num[i]?minprice,dp[i?1])$$
解释一下变量：

• $dp[i]$是指到了第i天，所能获取的最大利润，例如股票的价格是[1,2,4,1],那么$dp[0]=0,dp[1]=1,dp[2]=3,dp[3]=3$，这里dp[3]也等于3的原因是：第4天价格为1，$dp[3]=max(1?1,dp[2])=3$
• 我们所要比较的就是第i天所能获取的最大利润和第i-1天所能获取的最大利润。哪个大，哪个就是第i天所能获取的最大利润。

我们又找到了递推公式：
$$dp[i]=max(num[i]?minprice,dp[i?1])$$
我们只要找到minprice即可。

最终代码如下：

def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        dp=[0 for i in range(n)]#构造dp[]
        dp[0]=0#dp[i]的初始值
        minprice=prices[0]
        maxp=0
        i=1
        while i<n:
            minprice=min(minprice,prices[i])#到第i天股票的历史最低价是多少
            dp[i]=max(prices[i]-minprice,dp[i-1])#计算第i天为止最高利润
            maxp=max(maxp,dp[i])#计算最高利润
            i+=1
        return maxp

结果如下：

2.3 机器人寻路问题

leetcode:62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

这道题就留给大家思考吧，需要注意以下几个点：

• 这是一个二维dp[]
• 如何实现只往下或者右走？
• 递推关系式是什么？
• 初始值是什么？

3. 总结

动态规划解决问题对看问题的角度有着独特的方式，开始学习可能会觉得别扭，但是经过一些题的训练，你就会找到最优子结构、无后效性等动态规划的特征，总而言之，多理解，多动手练习，动态规划不是问题！

4.参考资料

《leetcode官网》