本文最后更新于:2 个月前

一、动态规划

1、从斐波那契数列说起

斐波那契数列我们比较熟悉了,它的递推公式为$f(n)=f(n-1)+f(n-2)$,它的解法在《数据结构与算法——递归》这一节里也说过了。直接使用递归会造成很多重复计算,它的时间复杂度为$O(2^N)$;而使用记忆化,即将中间过程缓存起来,可以降到$O(N)$的时间复杂度。实际上这样的递归是“从上而下”的,我们可以“从下而上”地做,由$f(0)$和$f(1)$得到$f(2)$,再由$f(1)$和$f(2)$得到$f(3)$……这样的写法如下所示:

F[0], F[1] = 0, 1
for i in range(2, n):
	F[i] = F[i-1] + F[i-2]

上面的“由下而上地使用递推公式”代表了动态规划的基本思想。上面的斐波那契数列的解法,是最最简单的动态规划,实际上的递推公式会更复杂,比如会有各种限制条件。

动态规划的基本思想:问题的最优解如果可以由子问题的最优解推导得到,则可以先求解子问题的最优解,再构造原问题的最优解;若子问题有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解。[1]
状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个“状态”。[2]
状态转移方程:即递推公式。上面的斐波那契数列的递推公式是给定的,而一般情况下需要我们自己推导出来递推公式。

2、举例进一步说明

现在举个例子进一步说明动态规划:数路径问题。有下面一个$m$行$n$列的方格格,从最左上角的$(0, 0)$出发,达到最右下角的$(m-1, n-1)$,一共有几条路?图上颜色的格子是障碍物不能走,并且只能向右或向下走。

Sample

对于这个问题,我们可以递归地求解,如下图所示。从一开始,可以向右走到B,也可以向下走到A,那么从start到end的有多少条路径=从B到end的路径数+从A到end的路径数。同样从B到end的路径数=从E到end的路径数+从C到end的路径树,对于A也是类似的,这样可以一直递归下去。但是这样会有个问题,和斐波那契数列的原始递归解法一样,有很多路径被重复计算了,比如从C到end的路径,它的时间复杂度也会是指数级的。

Sample

根据上节对斐波那契数列的分析,我们可以采用“自底向上”的方式,如下图所示,我们从end开始往前推。要到达end,只有从红色箭头指的两个格子那里走(因为只能向右走或向下走)。也就是说,当处于这两个格子之一的时候,只有一条路可以走,我们在格子里记“1”。对于最下面一排的格子,我们都只能向右走,所以都标记为“1”。从蓝色箭头指的格子出发,我们可以向右走也可以向下走,有两条路所以标记为“2”。这个“2”其实是右边格子到end的路径数+下面格子到end的路径数,也就是“1+1”。同理,白色箭头指的格子应该标记为1+1=2,也有两条路可走;绿色箭头指的格子应该标记为2+1=3,则有3条路可走。

Sample

就这样从end开始一直往上遍历每个格子,我们可以把格子都标记上,一直到start。最后start右边是17,下边是10,因此这个题的结果就是27。

Sample

动态规划模板:

# 以二维为例,只是一个大概的框架
def DP():
	# 定义状态
	dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	# 状态初始化
	dp[0][0], dp[0][1], ... = x, y, ...
	# DP状态的推导
	for i in range(m):
		for j in range(n):
			dp[i][j] = min(dp[i-1][j], dp[i][j-1])
	return dp[m][n]	# 最优解

二、例题

1、爬楼梯

此题为leetcode第70题

Sample

假设我们现在在第n个阶梯,我们要求的是走到第n个阶梯有多少种走法,即$F(n)$。我们知道只能走1步或2步,那么要走到第n个阶梯,只能从第n-1个阶梯或第n-2个阶梯走,那么走到第n个阶梯的走法个数等于走到第n-1个阶梯的走法个数加上走到第n-2个阶梯的走法个数。上述过程我们可以总结出此题的状态及状态转移方程:

  • 状态:$F(n)$,到第n个阶梯的走法个数
  • 状态转移方程:$F(n)=F(n-1)+F(n-2)$
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for i in range(2, n):
            c = a + b
            b, a = c, b
        return c
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

2、三角形最小路径和

此题为leetcode第120题

Sample Sample

三角形是个二维数组,我们要求得从最上面的$(0, 01)$出发,到最底下一层的最小路径和,即DF(0, 0)。比如上图的最小路径和的路径是$2 \to 3 \to 5 \to 1$。此题不可以用贪心算法,反例如上面右图所示。要用动态规划,我们要从底向上地去思考。加入我们处于第$i$行,那么从$(i, j)$出发到底部的最小路径和为:(它的左下方格的最小路径和,它的右下方格的最小路径和)的最小值加上它自己。注意我们需要得到是“最小路径和”,而不是方格本身的最小值。由此我们可以确定本题的状态和状态转移方程:

  • 状态:$DF(i, j)$,第$(i, j)$个方格到最底部的最小路径和
  • 状态转移方程:$DF[i, j] = min(DF[i+1, j], DF[i+1,j+1]) + Triangle[i, j]$,初始值为$DF[m-1, j]=Triangle[-1, j]$
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        m, n = len(triangle), len(triangle[-1])
        DP = triangle[-1]
        for i in range(m-1)[::-1]:
            for j in range(len(triangle[i])):
                DP[j] = min(DP[j], DP[j+1]) + triangle[i][j]
        return DP[0]
  • 时间复杂度:$O(m \times n)$
  • 空间复杂度:$O(n)$

3、乘积最大子序列

此题是leetcode第152题
我们设有一个数组a=[2, 3, -2, 4],其乘积最大的子序列为2, 3,最大乘积为6。假设我们在第i位,因为这个数可能为正也可能为负,所以我们需要记录最大乘积子序列和最小乘积子序列。我们可以这样定义状态和状态转移方程:

  • 状态:$DP_{max}[i]$和$DP_{min}[i]$。代表的意思是,在第$i$个数时,从$0 \to i$的最大乘积子序列的乘积值,注意这里包括第$i$个数。
  • 状态转移方程:因为$a[i]$可能为正也可能为负,为负时要乘前面的最小子序列的乘积才能变为最大值,因此要区分$a[i]$为正负的情况:

最后的结果为$max\{DP_{max}\}$

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if nums is None:
            return None
        # 这里我们不需要为nums里的每个元素都开辟一个存储最大最小值的空间
        # 只需要当前元素和前一个元素的就行
        DP_max, DP_min, res = [nums[0], nums[0]], [nums[0], nums[0]], nums[0]
        for i in range(1, len(nums)):
            num = nums[i]
            x, y = i % 2, (i - 1) % 2
            DP_max[x] = max(DP_max[y] * num, DP_min[y] * num, num)
            DP_min[x] = min(DP_max[y] * num, DP_min[y] * num, num)
            res = max(DP_max[x], res)
        return res
  • 时间复杂度:$O(N^2)$
  • 空间复杂度:$O(1)$

4、最长上升子序列

此题为leetcode第300题
假设有一序列a=[10, 9, 2, 5, 3, 7, 101, 18, 20],其最长上升子序列为2, 3, 7, 18, 20,长度为5。假如我们处于第$i$个位置,对于它前面的每个元素$j$,都有个从0到$j$的最长上升子序列长度,如果$a[i]>a[j]$,那么$a[0]$到$a[j]$的最长上升子序列再加上$a[i]$通用可以构成上升序列。所以对应每个$j$,我们找到他们当中加上$a[j]$后最长上升子序列的长度即可。

  • 状态:$DP[i]$,从0到$i$的最长上升子序列的长度(包含第$i$个元素)
  • 状态转移方程:对于$i \in[0, n-1]$,$DP[i]=max\{DP[i], DP[j]+1\}$,其中$j \in [0, i-1]$且$a[j] < a[i]$

最后的结果为$max\{DP[0], DP[1], \cdots, DP[n-1]\}$

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 0
        
        DP = [1] * len(nums)
        res = 1
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    DP[i] = max(DP[j] + 1, DP[i])
            res = max(DP[i], res)
        return res

5、零钱兑换

此题为leetcode第322题
设有不同面额的硬币coins=[1, 2, 5],和一个总金额amount=11。这个题可以转为类似爬楼梯的问题(上面第1题),每次可以爬1、2、5步,一共有11级台阶,所需的最少步数是多少。

  • 状态:$DP[i]$,到达第$i$阶时最少的步数
  • 状态转移方程:$DP[i]=min\{DP[i-coins[j]]\} +1,j \in [0, n-1] \space \space \text{and} \space \space coins[j] \leq i$

最终结果为$DP[amount]$

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
    	# 初始化一个长度为amount + 1的数组
        DP = [0] + [amount+1] * (amount)
        for i in range(1, amount+1):
            for coin in coins:
                if coin <= i:
                    DP[i] = min(DP[i], DP[i-coin] + 1)
        if DP[amount] > amount:	# 说明DP[i]没有被更新,没有可以组成amount的组合
            return -1
        else:
            return DP[amount]
  • 时间复杂度:$O(amount \times n)$
  • 空间复杂度:$O(amount)$

6、编辑距离

此题为leetcode第72题
有两个单词word1word2,假设我们处于word1的第$i$位和word2的第$j$位,分为两种情况。第一种情况,$w[i]==w[j]$,此时不需要任何变化,此时的最少的操作数为word1的第0到i-1个字符变为word2第0至j-1个字符所需的最少操作数第二种情况,$w[i]!=w[j]$,那么可能执行三种操作(插入,删除,替换)。如果执行插入操作,那么到此步需要懂得最少操作数为word1的第0至i-1个字符变为word2第0至j个字符所需的最少操作数;如果执行删除操作,那么到此步需要懂得最少操作数为word1的第0至i个字符变为word2第0至j-1个字符所需的最少操作数;如果执行替换操作,那么和第一种情况是类似的。那到底选哪种操作呢,答案是选择使得当前状态最小的操作,即上面的三个操作中取$min$。
在这里插入图片描述

  • 状态:$DP[i][j]$,word1的前$i$个字符变为word2的前$j$个字符所需的最少步数
  • 状态转移方程:

最终结果为$DP[m][n]$

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        
        # 初始化一个二维数组,为(m+1) x (n+1)大小
        DP = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        # 初值
        # word1的第0至i个字符变为空需要i步操作
        # word1由空变为word的第0至j个字符需要j步操作
        for i in range(m + 1): DP[i][0] = i
        for j in range(n + 1): DP[0][j] = j
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    DP[i][j] = DP[i - 1][j - 1]
                else:
                    DP[i][j] = min(DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1]) + 1
        return DP[m][n]
  • 时间复杂度:$O(m \times n)$
  • 空间复杂度:$O(m \times n)$

7、股票买卖问题

这里我们讲解关于股票买卖的6道系列题:121122123188309714。以上题目均可以用一个状态转移方程解决,只需稍微修改既可以。我们以一个通用的情况为例,即“每天可以完成$K$笔交易”。注意:(1)一次交易是包括买和卖的过程;(2)当前有股票时只能卖,不能再次买入

我们设数组$a$的长度为$N$,我们可以设状态为到第$i$天时所获得的最大利润,是一个一维数组。但我们会发现,在写状态转移方程时无法判断当前有无股票(无法判断当前应该买还是卖)、无法判断当前是第几次交易(达到最大交易次数则无法再交易),因此上面两个信息也应该出现在状态里。那么我们需要定义一个三维的状态:

  • 状态的定义:$DP[i][k][j]$,到第$i$天时的最大利润。其中:(1)$k \in [0, K]$,表示$i$之前总共进行了多少次交易;(2)$j=0 \space or \space 1$,0表示当前无股票,只能不动或买,1表示当前有股票,只能不动或卖。

  • 状态转移方程:当处于第$i$天第$k$次交易时,可能出现有股票也可能无股票的情况,即$j$可取值为0或1。当$j=0$即没有股票时,可能是前一天也没有股票,当下也不做交易;也可能是前一天有股票,当下把它卖掉了,注意前一天有股票依然是第$k$次交易,因为只有再次卖掉才算一次交易。同理当$j=1$即有股票时,可能是前一天有股票,当下不做交易;也可能是前一天无股票,当下买入了,注意前一天无股票那么就是已经完成了$k-1$次交易。

最终结果为$max\{DP[n-1, k, 0], k \in [0, K]\}$。在这样的状态和状态转移方程下,时间复杂度为$O(N \times K)$,空间复杂度为$O(N \times K)$。

用这么一个状态转移方程就可以解决下面6道类似的题目:

188题: 最多可以完成$K$笔交易

class Solution:
    def maxProfit(self, K: int, prices: List[int]) -> int:
    	# 特殊情况,只有0天或1天无法完成一次完整的交易,利润为0
        if len(prices) <= 1:
            return 0
        # 这里需要对K进行一下讨论:若K大于prices长度的一半,那么实际上可以进行不限次数的交易,和122题的情况一样
        # 不区分这样的情况也可以,但在leetcode上会超时
        if K < len(prices) // 2:
        	# 定义状态,三维数组
            DP = [[[0, 0] for _ in range(K + 1)] for _ in range(len(prices))]
            # 初始化状态,第0天的每次交易有股票的情况下,利润为-prices[0]
            for k in range(1, K+1):
                DP[0][k][1] = -prices[0]
            # 根据状态方程遍历每天和每天的交易次数
            res = 0
            for i in range(1, len(prices)):
                for k in range(1, K+1):
                    DP[i][k][0] = max(DP[i-1][k][0], DP[i-1][k][1] + prices[i])
                    DP[i][k][1] = max(DP[i-1][k][1], DP[i-1][k-1][0] - prices[i])

                    if res < DP[i][k][0]:
                        res = DP[i][k][0]
            return res
        # 和122题一样的情况,解释见下面的122题
        else:
            DP = [0, -prices[0]]
            for price in prices[1:]:
                DP[0] = max(DP[0], DP[1] + price)
                DP[1] = max(DP[1], DP[0] - price)
            return DP[0]

121题:只能进行一次交易

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        # 只能进行一次交易的话可以把K这一维去掉,同时我们只关注相邻的状态,DP的空间复杂度可以由O(N)变为O(1)
        DP = [0, -prices[0]]
        for price in prices[1:]:
            DP[0] = max(DP[0], DP[1] + price)
            DP[1] = max(DP[1], -price)
        return DP[0]

122题: 可以交易无限次

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        DP = [0, -prices[0]]
        # 可以交易无限次的话K这个维度也没有意义了,可以去掉
        for price in prices[1:]:
            DP[0] = max(DP[0], DP[1] + price)
            DP[1] = max(DP[1], DP[0] - price)
        return DP[0]

123题: 最多可以完成2笔交易

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        # 是188题的特殊情况,可以直接设K=2
        K = 2
        DP = [[[0, 0] for _ in range(K + 1)] for _ in range(len(prices))]
        for k in range(1, K+1):
            DP[0][k][1] = -prices[0]
        res = 0
        for i in range(1, len(prices)):
            for k in range(1, K+1):
                DP[i][k][0] = max(DP[i-1][k][0], DP[i-1][k][1] + prices[i])
                DP[i][k][1] = max(DP[i-1][k][1], DP[i-1][k-1][0] - prices[i])

                if res < DP[i][k][0]:
                    res = DP[i][k][0]
        return res

309题: 不限交易次数,但有一天冷冻期,即卖出股票后,你无法在第二天买入股票

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        DP = [0, -prices[0]]
        prev_prev = 0	# 只有在前前一天卖掉后才能买
        for price in prices[1:]:
            temp = DP[0]	# 用一个临时变量保存前一天的DP[0]
            DP[0] = max(DP[0], DP[1] + price)
            DP[1] = max(DP[1], prev_prev - price)
            prev_prev = temp	# 当前操作完成后,temp就成了前前一天
        return DP[0]

714题: 不限交易次数,但买的时候有交易费。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if len(prices) <= 1:
            return 0
        # 整体和122题一样
        DP = [0, -prices[0]-fee]	# 在买的时候减去交易费
        for price in prices[1:]:
            DP[0] = max(DP[0], DP[1] + price)
            DP[1] = max(DP[1], DP[0] - price - fee)	# 买的时候减去交易费
            
        return DP[0]

总结

动态规划的题目最重要的是定义好状态状态转移方程,同时要注意边界条件

参考文献

[1] https://www.cnblogs.com/hithongming/p/9229871.html
[2] https://blog.csdn.net/ailaojie/article/details/83014821