devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划（DP）的原理、实现及应用_动态规划的核心是什么原理的应用

作者：花生_TL007 | 2024-05-14 05:42:46

赞

踩

动态规划的核心是什么原理的应用

文章目录

 

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

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

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


输出： 55
  • 1

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

性能测试

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

  1. import time
  2. n = 40
  3. tic = time.clock()
  4. res = fib(n)
  5. toc = time.clock()
  6. print('fib({}) = {}'.format(n,res))
  7. print('runtime: {}s '.format(toc-tic))

我们看下n=10的结果：

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

再看下 n=40 时的结果：

  1. fib(40) = 102334155
  2. runtime: 40.73219172568648s

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

原因分析

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

2. 记忆化搜索

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

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

 

fib(40)的测试结果：

  1. fib(40) = 102334155
  2. 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)

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

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

看下测试结果：

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

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

最优子结构

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

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

好，介绍完毕。

总结一下这几个解法：

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

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

几个例题

LeetCode 70 Climbing Stairs

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

LeetCode上 其他相似的例题：
在这里插入图片描述
在这里插入图片描述

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. 这里存在重叠子问题，如下图中蓝块。
    在这里插入图片描述
    思路： 递归、记忆化搜索、动态规划
  1. 状态定义： v[n] 分割正数n的最大乘积
  2. 状态转移： v[n] = max( i×(n-i), i×v[n-i] ) for 1<=i<=n-1

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

  1. class Solution:
  2.     def integerBreak_rec(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: int
  6.         原生的递归方法：效率低
  7.         """
  8.         def breakInteger(n):
  9.             if n==1:
  10.                 return 1
  11.             res = -1
  12.             for i in range(1,n):
  13.                 # n = i + (n-i)
  14.                 res = max( res, i*(n-i), i*breakInteger(n-i) )
  15.             return res
  16.  
  17.         return breakInteger(n)
  18.  
  19.     def integerBreak_memo(self, n):
  20.         """
  21.         :type n: int
  22.         :rtype: int
  23.         第一种改进： 自上而下的记忆化搜索
  24.         """
  25.         def breakInteger(n):
  26.             if n==1:
  27.                 return 1
  28.             if memo[n] != -1:
  29.                 return memo[n]
  30.             res = -1
  31.             for i in range(1,n):
  32.                 # n = i + (n-i)
  33.                 res = max( res, i*(n-i), i*breakInteger(n-i) )
  34.             memo[n] = res
  35.             return res
  36.  
  37.         assert n>=2
  38.         memo = [-1 for i in range(n+1)]
  39.         return breakInteger(n)
  40.  
  41.     def integerBreak_dp(self, n):
  42.         """
  43.         :type n: int
  44.         :rtype: int
  45.         第二种改进：自底向上动态规划
  46.         """
  47.         assert n>=2
  48.         memo = [-1 for i in range(n+1)]
  49.  
  50.         memo[1] = 1
  51.         for i in range(2,n+1):
  52.             for j in range(1,i):
  53.                 memo[i] = max( memo[i], j*(i-j), j*memo[i-j] )
  54.                 
  55.         return memo[n]
  56.      
  57. if __name__ == '__main__':      
  58.     n = Solution().integerBreak_dp(10)
  59.     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 )
这个方法效率非常之低。

动态规划

考虑如下结构
在这里插入图片描述

  1. """
  2. 198. House Robber
  4. 转态定义：考虑偷取[x...n)范围里的房子
  5. 状态转移方程：
  6.             f(0) = max{ v(0)+f(2),
  7.                         v(1)+f(3),
  8.                         v(2)+f(4),
  9.                         ...
  10.                         v(n-3)+f(n-1),
  11.                         v(n-2),
  12.                         v(n-1)}  
  13. """
  14. class Solution:
  15.     def rob_rec(self, nums):
  16.         """
  17.         :type nums: List[int]
  18.         :rtype: int
  19.         递归方法
  20.         """
  21.         # 考虑抢劫nums[index:]范围内的所有房子
  22.         def tryRob(index)：
  23.             if index >= len(nums):
  24.                 return 0
  25.             res = 0
  26.             for i in range(index,len(nums)):
  27.                 res = max( res, nums[i]+tryRob(i+2) )
  28.             return res
  29.  
  30.         return tryRob(0)
  31.  
  32.     def rob_memo(self, nums):
  33.         """
  34.         :type nums: List[int]
  35.         :rtype: int
  36.         记忆化搜索
  37.         """
  38.         # 考虑抢劫nums[index:]范围内的所有房子
  39.         def tryRob(index)：
  40.             if index >= len(nums):
  41.                 return 0
  42.             if memo[index] != -1:
  43.                 return memo[index]
  44.  
  45.             res = 0
  46.             for i in range(index,len(nums)):
  47.                 res = max( res, nums[i]+tryRob(i+2) )
  48.             memo[index] = res
  49.             return res
  50.  
  51.         # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
  52.         memo = [-1 for i in range(n)]
  53.         return tryRob(0)
  54.  
  55.         
  56.     def rob_dp(self, nums):
  57.         """
  58.         :type nums: List[int]
  59.         :rtype: int
  60.         动态规划法
  61.         """
  62.         n = len(nums)
  63.         if n == 0:
  64.             return 0
  65.         
  66.         # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
  67.         memo = [-1 for i in range(n)]
  68.         memo[n-1] = nums[n-1]
  69.         
  70.         for i in range(n-2,-1,-1):
  71.             # memo[i]
  72.             for j in range(i,n):
  73.                 if j<n-2:
  74.                     memo[i] = max(memo[i],nums[j]+(memo[j+2]) 
  75.                 else:
  76.                     memo[i] = max(memo[i],nums[j]) # 末尾两个元素只能是自己
  77.                 
  78.         return memo[0]
  79.         
  80.         
  81. if __name__ == '__main__':          
  82. 	nums = [2,7,9,3,1]
  83. 	res = Solution().rob_dp(nums)   
  84. 	print(res)
  85.

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） 之 状态转移方程

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/567563
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号