动态规划（DP）的原理、实现及应用

矫情吗；* 2022-05-09 06:12 186阅读 0赞

### 文章目录 ###

*  1. 由一个例子说开： 斐波那契（fibonacci）数列
 *   *   *  性能测试
         *  原因分析
 *  2. 记忆化搜索
 *  3. 动态规划（Dynamic Programming，DP）
 *   *   *  最优子结构
         *  总结一下这几个解法：
         *  几个例题
         *   *  LeetCode 70 Climbing Stairs
 *  4. 动态规划的核心：状态与状态转移方程
 *   *  LeetCode 343 Integer Break
     *  LeetCode 198 House Robber
     *   *   *  暴力解法
             *  动态规划
             *  LeetCode上与此题相似的题目：
 *  5. 动态规划经典应用：背包问题
 *   *   *  三种解法
         *  背包问题动态规划解法的实现及优化
         *  背包问题的变种
         *  背包问题实例
         *   *  LeetCode上与此题相似的题目：
 *  6. 动态规划应用： 最长上升子序列（LIS）
 *   *   *  300 Longest Increasing Subsequence
         *  最长公共子序列: LCS问题
 *  7. 关于动态规划的其他：
 *  8. 如何用动态规划给出具体的解：返回去找

# 1. 由一个例子说开： 斐波那契（fibonacci）数列 #

**斐波那契数列**是由0和1开始，之后的数就是前两个数的和。  
首几个费波那契系数是：  
`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……`  
那我们如何用计算机来生成这些数呢，也就是说，求斐波那契数列第n位的值。  
很简单，用递归就可以了：

# 自上而下地递归
    def fib(n):
        if n in [0,1]:
            return n
        return fib(n-1) + fib(n-2)
        
    print(fib(10))

输出： 55

结果没有问题，接下来看一下递归性能如何。

### 性能测试 ###

写个简单的计时的测试代码：

import time
    n = 40
    tic = time.clock()
    res = fib(n)
    toc = time.clock()
    print('fib({}) = {}'.format(n,res))
    print('runtime: {}s '.format(toc-tic))

我们看下`n=10`的结果：

fib(10) = 55
    runtime: 2.4462208330078283e-05s

再看下 `n=40` 时的结果：

fib(40) = 102334155
    runtime: 40.73219172568648s

我们发现：当n变大时，这段递归代码用时变得很久，而且性能是急剧下降。这是为什么呢？

### 原因分析 ###

拿fib(5)来举例，要计算fib(5)，得知道fib(4)的值，要计算fib(4)的值，又得知道fib(3)的值，以此类推，直到递归到底时，fib(0)=0。下图是个fib(5)求解的展开图，可以看到，这里面有很过的重复计算，比如浅粉色框框住的fib(2)就重复计算了三次，可想而知当n很大时，这些重复计算的次数将呈指数上升，这就是递归效率不高的原因——**重叠子问题**。  
![fib(5)示意图][fib_5]

--------------------

# 2. 记忆化搜索 #

改进方法就是，将计算过的fib()值存储下来，下次用到直接查就行，这种方法叫**记忆化搜索**。  
于是在递归代码的基础上可以很轻松地改写成记忆化搜索，代码如下：

# 记忆化搜索：自上而下地求解
    def fib_memo(n):
        def fib(n):
            if n in [0,1]:
                return n
            # 如果memo数组中没有计算过fib(n)，则需计算一下并存到memo[n]中
            if memo[n] == -1:
                memo[n] = fib(n-1) + fib(n-2)
            return memo[n]
    
        memo = [-1 for i in range(n+1)]  # memo[0...n]中所有元素初始值为-1，表示未计算
        return fib(n)

fib(40)的测试结果：

fib(40) = 102334155
    runtime: 2.4746652798057767e-05s

经过简单的记忆化改造，效率由 40.7s 提升到了 0.0000247s ！  
记忆化搜索本质还是一种递归，只是用额外的变量来存储中间值而已，属于典型的空间换时间的方式。由于递归是一种自顶向下的方式，所以记忆化搜索也是一种自顶而下的搜索方法，即计算顺序是

fib(n) → fib(n-1) → fib(n-2) → ... → fib(1) → fib(0)

最后再从fib(0)一路回溯给fib(n)，done！

那么可不可以自底向上地算出斐波那契数列呢？当然有啊，这就是接下来要隆重请出的**动态规划**。

--------------------

# 3. 动态规划（Dynamic Programming，DP） #

思路很简单，知道了 fib(0) 和 fib(1)，就可以相加得fib(2)，fib(1)+fib(2)又得fib(3)，依次类推直到 fib(n)。自底向上的求解过程：

fib(0) → fib(1) → fib(2) → ... → fib(n-1) → fib(n)

没错，这也极其符合人的直观感觉，看着很舒服很顺眼。  
于是很容易写出代码：

# 动态规划：自下而上地解决问题
    def fib(n):
        memo = [-1 for i in range(n+1)]
        memo[0] = 0
        memo[1] = 1
        for i in range(2,n+1):
            memo[i] = memo[i-1] + memo[i-2]
        
        return memo[n]

看下测试结果：

fib(40) = 102334155
    runtime: 1.6782212696853094e-05s

`0.0000167s` 比记忆化搜索的 `0.0000247s` 又提高了一丢丢，这主要是因为记忆化搜索中多出了反复递归的开销。

### 最优子结构 ###

其实fib数列不是重点，重点是这个：这里面fib(2)是fib(3)的子问题，fib(3)又是fib(4)的子问题，以此类推，所以这是一个通过子问题推得原问题的过程。我们可以把上面的过程总结为这句话：**通过求子问题的最优解，可以获得原问题的最优解。**  
这里的子问题称为**最优子结构**。  
好，接下类引出**动态规划**的定义：

> 将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

好，介绍完毕。

### 总结一下这几个解法： ###

在递归问题中如果存在重叠子问题，那么就可以进行以下两种改造：

1.  自顶而下地解决问题：**记忆化搜索**
2.  自底而上地解决问题：**动态规划**  
    ![动态规划][70]

### 几个例题 ###

#### LeetCode 70 Climbing Stairs ####

![LeetCode 70. 爬楼梯][LeetCode 70.]  
解析：要爬到n阶台阶，有 ①从n-1阶再爬一阶到达 ②也可从n-2阶再爬2阶到达，这两种方式，所以爬到n阶的方法数等于爬到n-1阶的方法数与爬到n-2的方法数的和。接下来，n-1阶的方法数也等于n-2阶的加上n-3阶的，以此类推直到爬1阶和爬0阶。所以，**这个问题本质就是一个fibonacci数列的求解！** 而且这里面也存在很多重复计算的子块，例如下图蓝色子块。同上面的代码一样，这个问题完全可以用原生的递归方法、记忆化搜索和动态规划求解的。  
![爬楼梯][70 1]

LeetCode上 其他相似的例题：  
![在这里插入图片描述][70 2]  
![在这里插入图片描述][70 3]

--------------------

# 4. 动态规划的核心：状态与状态转移方程 #

前面我们将动态规划描述为一种 **通过求子问题的最优解，从而求得原问题的最优解** 的方法，那么有人可能会问了：

1.  如何将原问题切分成子问题？
2.  又怎么将子问题的解延伸回原问题，也就是说子问题和原问题是怎么连接起来的？

对于问题1，如何切分子问题，在DP中被称为**状态的定义**，其中**子问题**被称为**状态**。  
对于问题2:，如何从子问题到原问题，在DP被称为**状态转移方程**。

这两个东西才是动态规划的核心。

到底是怎么回事，直接拿LeetCode上两个例子说话：

## LeetCode 343 Integer Break ##

![LeetCode 343 Integer Break][]  
**解析：**

1.  我们定义 **v\[n\]** 分割正数n的最大乘积 ，这是**状态的定义**。
2.  每次将n分解为两个数的和，如：1+(n-1), 2+(n-2), 3+(n-3)…，对于每一种分割 **i+(n-i)**，最大乘积 **v\[n\]** 的来源于 **i** 和 **n-i** 的乘积 和 **i** 和 **v\[n-i\]** 的乘积 中较大的那个，而最终的最大v\[n\]是在所有 **1<=i<=n**上最大的那个，即**v\[n\] = max( i×(n-i), i×v\[n-i\] ) for 1<=i<=n-1** ，这就是从**v\[n-1\]** 到 **v\[n\]** 的**状态转移方程**。
3.  这里存在重叠子问题，如下图中蓝块。  
    ![在这里插入图片描述][70 4]  
    **思路：** 递归、记忆化搜索、动态规划

> 1.  状态定义： **v\[n\]** 分割正数n的最大乘积
> 2.  状态转移： **v\[n\] = max( i×(n-i), i×v\[n-i\] ) for 1<=i<=n-1**

**代码**  
我将递归、记忆化搜索和动态规划三种方法放在了一个类中：

class Solution:
        def integerBreak_rec(self, n):
            """
            :type n: int
            :rtype: int
            原生的递归方法：效率低
            """
            def breakInteger(n):
                if n==1:
                    return 1
                res = -1
                for i in range(1,n):
                    # n = i + (n-i)
                    res = max( res, i*(n-i), i*breakInteger(n-i) )
                return res
    
            return breakInteger(n)
    
        def integerBreak_memo(self, n):
            """
            :type n: int
            :rtype: int
            第一种改进： 自上而下的记忆化搜索
            """
            def breakInteger(n):
                if n==1:
                    return 1
                if memo[n] != -1:
                    return memo[n]
                res = -1
                for i in range(1,n):
                    # n = i + (n-i)
                    res = max( res, i*(n-i), i*breakInteger(n-i) )
                memo[n] = res
                return res
    
            assert n>=2
            memo = [-1 for i in range(n+1)]
            return breakInteger(n)
    
        def integerBreak_dp(self, n):
            """
            :type n: int
            :rtype: int
            第二种改进：自底向上动态规划
            """
            assert n>=2
            memo = [-1 for i in range(n+1)]
    
            memo[1] = 1
            for i in range(2,n+1):
                for j in range(1,i):
                    memo[i] = max( memo[i], j*(i-j), j*memo[i-j] )
                    
            return memo[n]
         
    if __name__ == '__main__':      
        n = Solution().integerBreak_dp(10)
        print(n)

LeetCode上与此题相似的题目：

*  **279 Perfect Squares**  
    给定一格正整数n，寻找最少的完全平方数，使他们的和为n。
 *  **91 Decode Ways**  
    数字字符串的解析
 *  **62 Unique Paths**  
    机器人从m×n的矩阵左上角出发到达右下角（每次只能向右或向下），共有多少种路径？
 *  **63 Unique Paths II**  
    （接上题）若矩阵中含有障碍物，此时共有多少种路径？

## LeetCode 198 House Robber ##

小偷洗劫一条街上的所有房子，每个房子有不同价值的把宝物，但不能连续抢劫俩相邻房子。求最多可以偷到多少宝物？

#### 暴力解法 ####

检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值，找最大值。  
时间复杂度: O( (2^n)\*n )  
这个方法效率非常之低。

#### 动态规划 ####

考虑如下结构  
![在这里插入图片描述][70 5]

"""
    198. House Robber
    
    转态定义：考虑偷取[x...n)范围里的房子
    状态转移方程：
                f(0) = max{ v(0)+f(2),
                            v(1)+f(3),
                            v(2)+f(4),
                            ...
                            v(n-3)+f(n-1),
                            v(n-2),
                            v(n-1)}  
    """
    class Solution:
        def rob_rec(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            递归方法
            """
            # 考虑抢劫nums[index:]范围内的所有房子
            def tryRob(index)：
                if index >= len(nums):
                    return 0
                res = 0
                for i in range(index,len(nums)):
                    res = max( res, nums[i]+tryRob(i+2) )
                return res
    
            return tryRob(0)
    
        def rob_memo(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            记忆化搜索
            """
            # 考虑抢劫nums[index:]范围内的所有房子
            def tryRob(index)：
                if index >= len(nums):
                    return 0
                if memo[index] != -1:
                    return memo[index]
    
                res = 0
                for i in range(index,len(nums)):
                    res = max( res, nums[i]+tryRob(i+2) )
                memo[index] = res
                return res
    
            # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
            memo = [-1 for i in range(n)]
            return tryRob(0)
    
            
        def rob_dp(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            动态规划法
            """
            n = len(nums)
            if n == 0:
                return 0
            
            # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
            memo = [-1 for i in range(n)]
            memo[n-1] = nums[n-1]
            
            for i in range(n-2,-1,-1):
                # memo[i]
                for j in range(i,n):
                    if j<n-2:
                        memo[i] = max(memo[i],nums[j]+(memo[j+2]) 
                    else:
                        memo[i] = max(memo[i],nums[j]) # 末尾两个元素只能是自己
                    
            return memo[0]
            
            
    if __name__ == '__main__':          
    	nums = [2,7,9,3,1]
    	res = Solution().rob_dp(nums)   
    	print(res)

#### LeetCode上与此题相似的题目： ####

*  **213 House Robber II**  
    此处将街道改为环形街道，即最后一个元素和第一个元素为邻居。求窃得财产的最大值。
 *  **337 House Robber III**  
    此处将街道给为小区，小区是二叉树结构，即不能同时选择相邻节点。
 *  **309 Best Time to Buy and Sell Stock with Cooldown**  
    股票买卖时机的选择，使利润最大化。

--------------------

# 5. 动态规划经典应用：背包问题 #

在动态规划中，有类非常经典的问题称为0-1背包问题。有一个背包，容量是C，现有那种不同的物品，编号为0…n-1  
，其中每一件物品重量为**w(i)**,价值为**v(i)**。问可以向包中放哪些物品，使得在不超过背包容量的基础上，物品总价值最大。

### 三种解法 ###

**暴力解法**：每一件物品都可以放进或者不放进，遍历所有可能性。 时间复杂度O((2^n)\*n)。  
**贪心算法**：优先放入平均价值最大的物品，结果只是近似解，而不是最优解。  
**动态规划**：

> **状态**： F(n,C) 考虑将n个物品放进容量为C的背包，使得价值最大。(这里约束条件为n和C)  
> **状态转移方程**： F(i,C) = max( F(i-1,C), v(i)+F(i-1,C-w(i)) )  
> 对应 1.不放入第i个物品 2.放入第i个物品 这两种状态中值最大的那个。

### 背包问题动态规划解法的实现及优化 ###

时间复杂度为O(nC)已经几乎没有优化空间了，但是可以从空间复杂度上进行优化。

1.  **动态规划解法: n行版**  
    原始动态规划，建立一个n行C+1列的矩阵 memo\[n-1\]\[C+1\]  
    时间复杂度：O(nC)  
    空间复杂度：O(nC)
2.  **动态规划解法: 两行版**  
    改进1：由于第i行元素只依赖于第i-1行元素。理论上，memo只需要保证两行元素。  
    空间复杂度 O(2C)=O( C)
3.  **动态规划解法： 一行版**  
    改进2：由于某位置的元素只依赖于上一行的对应位置和上一行的左侧元素。所以可以从右边开始更新，这样memo只需一行就可以完成。  
    空间复杂度 O( C)

### 背包问题的变种 ###

*  **多重背包问题**：每个物品不止1个，有num(i)个
 *  **完全背包问题**：每个物品可以无限使用
 *  **多维费用背包问题**：要考虑物品的体积和重量两个维度（原问题上增加一个约束条件，memo数组变为三维即可）
 *  **物品间加入更多约束**：物品间可以相互排斥；也可以相互依赖

### 背包问题实例 ###

**416 Patition Equal Subset Sum** 分割等和子集

> 典型的背包问题：在n个物品中选出一定物品，填满sum/2的背包  
> 与原背包问题不同的是：我们不需要物品价值最大，目标是能填满。或者也可以理解为物品价值均为1。

#### LeetCode上与此题相似的题目： ####

*  **322 Coin Change**  
    给定不同面值的硬币，问需要多少硬币（可反复使用），可以凑成指定的金额？
 *  **377 Combination Sum IV**  
    给定一整数数组（无重复数字，但数字可重复使用），问有多少种可能，使用这个数组中的数字，凑成一个指定的整数target。
 *  **474 Ones and Zeros**
 *  **139 Word Break**  
    判断字符串数组中可否有不同字符串收尾相连组成target字符串。
 *  **494 Target Sum**  
    给定非0数字数组，在这些数前面加上+或-，使其结果为给定的整数S。

--------------------

# 6. 动态规划应用： 最长上升子序列（LIS） #

### 300 Longest Increasing Subsequence ###

给定一整数序列，求其中的最长上升子序列的长度。

*  方法1：动态规划解法  
    1. **状态定义**： **LIS(i)** 表示以第i个数字为结尾的最长上升子序列的长度。即表示\[0…i\]范围内，选择数组nums\[i\] 可以获得的最长上升子序列的长度  
    2. **状态转移**： LIS(i) = max( 1+LIS(j) if nums\[i\]>nums\[j\] for j<i )  
    时间复杂度O(n^2)
 *  方法2：二分搜索法  
    这里不做介绍。  
    时间复杂度O(nlogn)

LeetCode上与此题相似的题目：

*  **376 Wiggle Subsequence**  
    求最长轮流交替子序列

### 最长公共子序列: LCS问题 ###

给出两个字符串S1和S2，求这两个字符串的最长公共子序列的长度。  
**状态定义**：

> **LCS(m,n)** 是S1\[0…m\]和S2\[0…n\]的最长公共子序列的长度。

**转移方程**：

> 1.  **S1\[m\] == S2\[n\]： LCS(m,n) = 1+ LCS(m-1,n-1)**
> 2.  **S1\[m\] != S2\[n\]： LCS(m,n) = max(LCS(m-1,n),LCS(m,n-1))**

# 7. 关于动态规划的其他： #

*  动态规划其实相当常见，譬如 dijkstra单源最短路径算法也是动态规划
    
    > **状态定义**： shortestPath(i)为从start到i的最短路径长度  
    > **状态转移**： shortestPath(i) = min( shortestPath(i) + w(a->i))
 *  动态规划是一个非常大的问题范畴，因为它不仅他可以解决的问题是非常灵活的，还因为它是公认的在算法设计上艺术含量非常高的算法，因为动态规划似乎没有一个固定的套路。
 *  LeetCode上更多关于动态规划的问题，找dp标签的题。
 *  单论面试，面试中动态规划考察较少，更多的是考察更基础的问题，所以可以相对放松对LeetCode上动态规划题目的要求。

# 8. 如何用动态规划给出具体的解：返回去找 #

例1： 300. 最长上升子序列。  
例2： 0-1背包问题

References：  
[非常好的动态规划总结，DP总结][DP]  
[背包问题的总结][Link 1]  
[动态规划（dp） 之 状态转移方程][dp_ _]

[fib_5]: /images/20220509/9f1ee23d79a14cc1bbd21d1ddcc1a921.png
[70]: /images/20220509/a75d90a13bc442b8ad16b6f5aa464320.png
[LeetCode 70.]: /images/20220509/9930c5b445b84b54a99e781d5e3f4101.png
[70 1]: /images/20220509/483c2d51329a4302b657b93650253cf5.png
[70 2]: /images/20220509/72effe6cd52d483184c3a130e8d3d23a.png
[70 3]: /images/20220509/b7e53ca7704444e691de12bcb1c13723.png
[LeetCode 343 Integer Break]: /images/20220509/749ba4e4862641c9bdf559b937835012.png
[70 4]: /images/20220509/7794af5b96ed4163b9e71f9883b64da4.png
[70 5]: /images/20220509/2ce0fd01ad114b1196f3c1e92a4cbd21.png
[DP]: https://blog.csdn.net/mmc2015/article/details/73558346
[Link 1]: https://juejin.im/post/5b40c99ee51d45190b615f33
[dp_ _]: https://blog.csdn.net/xia842655187/article/details/47318243