-
2020-11-21 21:22:04
听到 动态规划 这个响亮的大名你可能已经望而却步,那是因为这个响亮的名字真的真的很具有迷惑性,不像递归、回溯和贪心等等算法一样,其文即其意,而动态规划则不同,很容易望文生义,真可谓害人不浅,今天我就带大家一起扒一扒 动态规划 的裤子。
第一点,大家在学习动态规划时切忌望文生义,因为其名字与其思想八竿子打不着。你可以自己起一个能让自己记住其思想的名字更好,比如递推公式法,状态转移方程法等等。
第二点,与其说动态规划是一个算法,还不如说是解决问题的方法论。
第三点,动态规划的一般形式就是求最优值,比如最长公共子序列、最大子段和、最优二叉搜索树等等。
废话不多说,进入正题!
动态规划的基本思想
动态规划算法与分治法类似,其基本思想就是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合动态规划法求解的问题,经分解得到的子问题往往不是相互独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费指数时间。然而,不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复结算了很多次。如果我们能够保存已经解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,从而得到多项式时间复杂度的算法。为了达到次目的,可以用一个表来记录所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动
更多相关内容 -
动态规划(DP)的原理、实现及应用
2018-10-03 01:56:084. 动态规划的核心:状态与状态转移方程 LeetCode 343 Integer Break LeetCode 198 House Robber 暴力解法 动态规划 LeetCode上与此题相似的题目: 5. 动态规划经典应用:背包问题 三种解法 背包问题动态规划解法的...文章目录
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很大时,这些重复计算的次数将呈指数上升,这就是递归效率不高的原因——重叠子问题。
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)的子问题,以此类推,所以这是一个通过子问题推得原问题的过程。我们可以把上面的过程总结为这句话:通过求子问题的最优解,可以获得原问题的最优解。
这里的子问题称为最优子结构。
好,接下类引出动态规划的定义:将原问题拆解成若干个子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。
好,介绍完毕。
总结一下这几个解法:
在递归问题中如果存在重叠子问题,那么就可以进行以下两种改造:
- 自顶而下地解决问题:记忆化搜索
- 自底而上地解决问题:动态规划
几个例题
LeetCode 70 Climbing Stairs
解析:要爬到n阶台阶,有 ①从n-1阶再爬一阶到达 ②也可从n-2阶再爬2阶到达,这两种方式,所以爬到n阶的方法数等于爬到n-1阶的方法数与爬到n-2的方法数的和。接下来,n-1阶的方法数也等于n-2阶的加上n-3阶的,以此类推直到爬1阶和爬0阶。所以,这个问题本质就是一个fibonacci数列的求解! 而且这里面也存在很多重复计算的子块,例如下图蓝色子块。同上面的代码一样,这个问题完全可以用原生的递归方法、记忆化搜索和动态规划求解的。
LeetCode上 其他相似的例题:
4. 动态规划的核心:状态与状态转移方程
前面我们将动态规划描述为一种 通过求子问题的最优解,从而求得原问题的最优解 的方法,那么有人可能会问了:
- 如何将原问题切分成子问题?
- 又怎么将子问题的解延伸回原问题,也就是说子问题和原问题是怎么连接起来的?
对于问题1,如何切分子问题,在DP中被称为状态的定义,其中子问题被称为状态。
对于问题2:,如何从子问题到原问题,在DP被称为状态转移方程。这两个东西才是动态规划的核心。
到底是怎么回事,直接拿LeetCode上两个例子说话:
LeetCode 343 Integer Break
解析:- 我们定义 v[n] 分割正数n的最大乘积 ,这是状态的定义。
- 每次将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] 的状态转移方程。
- 这里存在重叠子问题,如下图中蓝块。
思路: 递归、记忆化搜索、动态规划
- 状态定义: v[n] 分割正数n的最大乘积
- 状态转移: 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 )
这个方法效率非常之低。动态规划
考虑如下结构
""" 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)已经几乎没有优化空间了,但是可以从空间复杂度上进行优化。
-
动态规划解法: n行版
原始动态规划,建立一个n行C+1列的矩阵 memo[n-1][C+1]
时间复杂度:O(nC)
空间复杂度:O(nC) -
动态规划解法: 两行版
改进1:由于第i行元素只依赖于第i-1行元素。理论上,memo只需要保证两行元素。
空间复杂度 O(2C)=O( C) -
动态规划解法: 一行版
改进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]的最长公共子序列的长度。
转移方程:
- S1[m] == S2[n]: LCS(m,n) = 1+ LCS(m-1,n-1)
- 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) 之 状态转移方程 -
动态规划的基本原理
2020-02-22 13:36:51动态规划的基本原理 能用动态规划解决的问题的特点 问题具有最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。 无后效性:当前的若干个状态值一旦确定,则...动态规划的基本原理
能用动态规划解决的问题的特点
-
问题具有最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。
-
无后效性:当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取那种手段、哪条路径演变到当前的这若干个状态无关。事实上,不满足无后效性的问题分解是写不出状态转移方程的。不过这也与我们分划问题涉及状态的艺术有关。
动态规划解题的一般思路
-
将原问题分解为n个子问题:将原问题分解为若干个子问题,子问题和原问题形式相同或者类似,只不过规模变小。当子问题全都解决时,原问题即解决。子问题的解一旦求出就被保存,所以每个子问题只需要求解一次。
-
确定状态:用动态规划解题,经常碰到的情况是,K个整形变量能构成一个状态,我们用一个K维的数组来存储各个状态的值。注意这里的值并不一定是一个数,而可能是结构体等。一个状态下的值通常是一个或者多个子问题的解
-
确定一些初始状态(边界条件)的值
- 如果使用记忆化搜索,即设置递归出口,
- 如果使用递推,就需要将这些值填入
dp
数组
-
确定状态转移方程:求出不同状态之间是如何迁移的,即如何从一个或者多个值已知的状态,求出另一个状态的值。状态的迁移通常可以用递推公式表示,该公式就是状态迁移方程。
具体实现
-
记忆化搜索
- 直接按照递归函数的思路完成编写,只是在函数的头部增加快捷返回出口,函数return前存储值。
- dp数组:递归函数有n个参数,就定义一个n维的数组,数组的下标最大值是递归函数参数的取值范围
- 也就是说,我们把每一种参数对应的值都开一个空间存起来。
-
递推
-
根据我们的递推公式来判断循环递推的方向。如果递推公式涉及的元素是不断增大的,那么就从小开始递推不断增大,反之则从大开始不断减小
比如 d p [ r ] [ j ] = m a x ( d p [ r + 1 ] [ j ] , d p [ r + 1 ] [ j + 1 ] ) + n u m [ r ] [ j ] ; dp[r][j] = max(dp[r + 1] [j], dp[r +1] [j + 1]) + num[r] [j]; dp[r][j]=max(dp[r+1][j],dp[r+1][j+1])+num[r][j];
这个递推公式涉及的元素r、j都不断增大,那么我们就应该从小到大递推
-
确定递推的边界条件。最初始的一些值我们需要提前在dp数组中初始化好,同时还要设置一些递推的非法出口的值。非法出口的设置需要保证:永远不可能用到这个出口来更新某个dp,故而我们应使用反向意义来设置非法出口
非法出口类同于递归中出现超出范围、显然不再可能可以完成任务的参数的情况的return
反向意义:例如我们求最小值,非法出口就应定义为99999999
-
在递推中,当我们在求 d p [ r ] [ j ] dp[r][j] dp[r][j]时,我们必须已经求出了所有r、j之前的dp值,故而判断递推的方向和边界条件非常重要
-
用一个N层循环来递推,N为dp数组的维数,从边界值开始,逐步填充数组,前一个阶段的解,为后阶段的求解提供有用的信息
-
使用递推的时候虽然快,但是要考虑的东西却很多很多,有一些局部细节和临界条件的考虑非常重要,有时候记忆化搜索能AC递推却WA就是因为有一些极限情况没有考虑到
-
-
-
什么是动态规划?动态规划的意义是什么?
2019-03-13 23:25:12以往见过许多教材,对动态规划(DP)的引入属于“奉天承运,皇帝诏曰”式:不给出一点引入,见面即拿出一大堆公式吓人;学生则死啃书本,然后突然顿悟。针对入门者的教材不应该是这样的。 现在,我们试着自己来一...0. intro
很有意思的问题。以往见过许多教材,对动态规划(DP)的引入属于“奉天承运,皇帝诏曰”式:不给出一点引入,见面即拿出一大堆公式吓人;学生则死啃书本,然后突然顿悟。针对入门者的教材不应该是这样的。
现在,我们试着自己来一步步“重新发明”DP。
1.从一个生活问题谈起
先来看看生活中经常遇到的事吧——假设您是个土豪,身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w,需要用到尽量少的钞票。
依据生活经验,我们显然可以采取这样的策略:能用100的就尽量用100的,否则尽量用50的……依次类推。在这种策略下,666=6×100+1×50+1×10+1×5+1×1,共使用了10张钞票。
这种策略称为“贪心”:假设我们面对的局面是“需要凑出w”,贪心策略会尽快让w变得更小。能让w少100就尽量让它少100,这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明,贪心策略是正确的。
但是,如果我们换一组钞票的面值,贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11,那么我们在凑出15的时候,贪心策略会出错: 15=1×11+4×1 (贪心策略使用了5张钞票) 15=3×5 (正确的策略,只用3张钞票)
为什么会这样呢?贪心策略错在了哪里?
鼠目寸光。
刚刚已经说过,贪心策略的纲领是:“尽量使接下来面对的w更小”。这样,贪心策略在w=15的局面时,会优先使用11来把w降到4;但是在这个问题中,凑出4的代价是很高的,必须使用4×1。如果使用了5,w会降为10,虽然没有4那么小,但是凑出10只需要两张5元。
在这里我们发现,贪心是一种只考虑眼前情况的策略。 那么,现在我们怎样才能避免鼠目寸光呢?
如果直接暴力枚举凑出w的方案,明显复杂度过高。太多种方法可以凑出w了,枚举它们的时间是不可承受的。我们现在来尝试找一下性质。
重新分析刚刚的例子。w=15时,我们如果取11,接下来就面对w=4的情况;如果取5,则接下来面对w=10的情况。我们发现这些问题都有相同的形式:“给定w,凑出w所用的最少钞票是多少张?”接下来,我们用f(n)来表示“凑出n所需的最少钞票数量”。
那么,如果我们取了11,最后的代价(用掉的钞票总数)是多少呢?
明显 ,它的意义是:利用11来凑出15,付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
依次类推,马上可以知道:如果我们用5来凑出15,cost就是 。
那么,现在w=15的时候,我们该取那种钞票呢?当然是各种方案中,cost值最低的那一个!- 取11:
- 取5:
- 取1:
显而易见,cost值最低的是取5的方案。我们通过上面三个式子,做出了正确的决策!
这给了我们一个至关重要的启示—— f(n)只与f(n-1),f(n-5),f(n-11) 相关;更确切地说:f(n)=min{f(n-1),f(n-5),f(n-11)}+1;
这个式子是非常激动人心的。我们要求出f(n),只需要求出几个更小的f值;既然如此,我们从小到大把所有的f(i)求出来不就好了?注意一下边界情况即可。代码如下:
我们以 的复杂度解决了这个问题。现在回过头来,我们看看它的原理:f(n)只与f(n-1),f(n-5),f(n-11)的值有关。我们只关心f(w) 的值,不关心是怎么凑出w的。
这两个事实,保证了我们做法的正确性。它比起贪心策略,会分别算出取1、5、11的代价,从而做出一个正确决策,这样就避免掉了“鼠目寸光”!
它与暴力的区别在哪里?我们的暴力枚举了“使用的硬币”,然而这属于冗余信息。我们要的是答案,根本不关心这个答案是怎么凑出来的。譬如,要求出f(15),只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).我们能这样干,取决于问题的性质:求出f(n),只需要知道几个更小的f©。我们将求解f©称作求解f(n)的“子问题”。
这就是DP(动态规划,dynamic programming).
将一个问题拆成几个子问题,分别求解这些子问题,即可推断出大问题的解。思考题:请稍微修改代码,输出我们凑出w的方案。2 几个简单的概念**【无后效性】**
一旦f(n)确定,“我们如何凑出f(n)”就再也用不着了。
要求出f(15),只需要知道f(14),f(10),f(4)的值,而f(14),f(10),f(4)是如何算出来的,对之后的问题没有影响。
“未来与过去无关”,这就是无后效性。
(严格定义:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。)
【最优子结构】
回顾我们对f(n)的定义:我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解,我们即可算出w=15的最优解。
大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”。
引入这两个概念之后,我们如何判断一个问题能否使用DP解决呢?
能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。3. DP的典型应用:DAG最短路
问题很简单:给定一个城市的地图,所有的道路都是单行道,而且不会构成环。每条道路都有过路费,问您从S点到T点花费的最少费用。
这个问题能用DP解决吗?我们先试着记从S到P的最少费用为f§.想要到T,要么经过C,要么经过D。从而
好像看起来可以DP。现在我们检验刚刚那两个性质:
- 无后效性:对于点P,一旦f§确定,以后就只关心f§的值,不关心怎么去的。
- 最优子结构:对于P,我们当然只关心到P的最小费用,即f§。如果我们从S走到T是
那肯定S走到Q的最优路径是
对一条最优的路径而言,从S走到沿途上所有的点(子问题)的最优路径,都是这条大路的一部分。这个问题的最优子结构性质是显然的。
既然这两个性质都满足,那么本题可以DP。式子明显为:
其中R为有路通到P的所有的点, w_{R→P} 为R到P的过路费。
代码实现也很简单,拓扑排序即可。4. 对DP原理的一点讨论【DP的核心思想】
DP为什么会快?
无论是DP还是暴力,我们的算法都是在可能解空间内,寻找最优解。
来看钞票问题。暴力做法是枚举所有的可能解,这是最大的可能解空间。 DP是枚举有希望成为答案的解。这个空间比暴力的小得多。
也就是说:DP自带剪枝。
DP舍弃了一大堆不可能成为最优解的答案。譬如:
15 = 5+5+5 被考虑了。
15 = 5+5+1+1+1+1+1 从来没有考虑过,因为这不可能成为最优解。
从而我们可以得到DP的核心思想:尽量缩小可能解空间。
在暴力算法中,可能解空间往往是指数级的大小;如果我们采用DP,那么有可能把解空间的大小降到多项式级。
一般来说,解空间越小,寻找解就越快。这样就完成了优化。
【DP的操作过程】
一言以蔽之:大事化小,小事化了。
将一个大问题转化成几个小问题;
求解小问题;
推出大问题的解。【如何设计DP算法】
下面介绍比较通用的设计DP算法的步骤。
首先,把我们面对的局面表示为x。这一步称为设计状态。
对于状态x,记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).找出f(x)与哪些局面有关(记为p),写出一个式子(称为状态转移方程),通过f§来推出f(x).
【DP三连】
设计DP算法,往往可以遵循DP三连:
我是谁? ——设计状态,表示局面
我从哪里来?
我要到哪里去? ——设计转移
设计状态是DP的基础。接下来的设计转移,有两种方式:一种是考虑我从哪里来(本文之前提到的两个例子,都是在考虑“我从哪里来”);另一种是考虑我到哪里去,这常见于求出f(x)之后,更新能从x走到的一些解。这种DP也是不少的,我们以后会遇到。
总而言之,“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个,就能设计出状态转移方程,从而写代码求解问题。前者又称pull型的转移,后者又称push型的转移。5.例题:
最长上升子序列
最长上升子序列(LIS)问题:给定长度为n的序列a,从a中抽取出一个子序列,这个子序列需要单调递增。问最长的上升子序列(LIS)的长度。
e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8,长度为6。
如何设计状态(我是谁)?
我们记 f(x)为以 a(x) 结尾的LIS长度,那么答案就是 max{f(x)}。
状态x从哪里推过来(我从哪里来)?
考虑比x小的每一个p:如果 ,那么f(x)可以取f§+1. 解释:我们把 接在 的后面,肯定能构造一个以 结尾的上升子序列,长度比以 结尾的LIS大1.那么,我们可以写出状态转移方程了:
至此解决问题。两层for循环,复杂度 .
从这个例题中可以看出,DP是一种思想,一种“大事化小,小事化了”的思想。带着这种思想,DP将会成为我们解决问题的利器。这篇博客是我在知乎看到后感觉很好转载整理过来的,之前对dp还是有点懵,看完以后有种茅塞顿开的感觉,这篇文章是上海洛谷有限公司讲师阮行止老师的原创。
-
C++动态规划详解
2021-09-11 18:30:59动态规划思想 一、动态规划概念: 动态规划(dp)是研究多步决策过程最优化问题的一种数学方法。在动态规划中,为了寻找一个问题的最优解(即最优决策过程),将整个问题划分成若干个相应的阶段,并在每个阶段都... -
编程实现动态规划求解多段图问题算法代码.zip
2020-05-23 11:11:18重点掌握:动态规划最优性原理、多段图问题求解。 编程实现动态规划求解多段图问题算法代码。 多段图问题是一种特殊的有向无环图的最短路径问题。其中产生从源点s到汇点t的最短路径的决策序列就是最优决策,此长度... -
面试必考字符串相关的动态规划——最大公共子序列、最大公共子串、编辑距离
2020-12-21 08:07:53字符串相关的动态规划最大公共子序列最大公共子串编辑距离 简述这三个算法解决的问题和展示状态转移方程并且给出可通过执行的Python代码。 最大公共子序列 子序列是,一个字符串中的任意字符组成的序列,重点在于,... -
动态规划算法原理及案例
2020-03-26 22:05:22动态规划基本概念 ...动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题。 基本思想:... -
动态规划算法的原理和实现(Java)
2019-10-31 17:03:10动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,... -
动态规划原理及其实现
2017-02-03 19:12:31原理 入门理论 最优化原理 问题求解模式 ...一些静态模型,只要人为地引进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。与此同时,他提出了解决这类问题的“最优化原理”(Pr -
详解动态规划算法
2020-04-09 07:59:47) 本文将会从以下角度来讲解动态规划: 什么是动态规划 动态规划从入门到进阶 再谈动态规划 什么是动态规划 以下是我综合了动态规划的特点给出的动态规划的定义:动态规划是一种多阶段决策最优解模型,一般用来求... -
力扣算法 Java 刷题笔记【动态规划篇 DP】hot100(一)动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5
2021-12-08 09:07:02文章目录 1. 什么是动态规划: 2. 求解动态规划 2.1 核心问题是穷举: 2.2 求状态转移方程框架 2.3 什么是状态转移方程 & 状态 3. 举例 3.1 斐波那契数 3.2 零钱兑换 -
05|面试即正义第一期:什么样的问题应该使用动态规划?
2022-05-05 10:31:44动态规划问题特点总结 -
算法-动态规划 Dynamic Programming--从菜鸟到老鸟
2017-07-15 22:58:29前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间... -
【动态规划】01背包问题(通俗易懂,超基础讲解)
2018-08-24 22:29:29通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优... -
动态规划及贪心算法
2020-02-22 08:39:47大家可能在公司里面都有一定的组织架构,可能有高级经理、经理、总监、组长然后才是小开发,今天我们通过这个例子,来讲讲什么问题适合使用动态规划。又到了一年一度的考核季,公司要挑选出三个最优秀的员工。一... -
动态规划(DP)
2022-01-08 13:38:29DP的思想,动态规划,更像是走一步规划一步,只要把问题规划为走一步规划一步,问题就可以逐步解决。 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除... -
动态规划算法之一——动态规划入门
2021-06-04 23:40:19动态规划核心2.动态规划算法局限3.动态规划算法应用场景4.站在巨人肩膀 用简单通俗易懂的话来记录自己对动态规划算法的理解 1.动态规划算法是什么 1.动态规划思想 动态规划算法与分治法类似,其基本思想也是将待求解... -
递归与动态规划
2021-12-12 10:11:13动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。 动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。 1、线性动规:拦截导弹,合唱队形... -
一文读懂动态规划算法原理,由浅入深
2019-07-29 09:47:07动态规划算法似乎是一种很高深莫测的算法,你会在一些面试或算法书籍的高级技巧部分看到相关内容,什么状态转移方程,重叠子问题,最优子结构等高大上的词汇也可能让你望而却步。 而且,当你去看用动态规划解决某个... -
什么是动态规划(Dynamic Programming)?动态规划的意义是什么?(1)
2020-07-15 10:16:12什么是动态规划(Dynamic Programming)?动态规划的意义是什么? 第一篇0. intro1. 从一个生活问题谈起2. 几个简单的概念3. 对DP原理的一点讨论5 例题最长上升子序列 注:本文源自知乎两篇文章,第一篇注重基础原理... -
动态规划之0/1背包问题原理详解: 简明、细致、深入理解
2022-04-23 22:29:30动态规划,0/1背包问题,回溯 -
强化学习——动态规划法
2021-12-05 09:51:31文章目录前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结 前言 提示:以下是本篇文章正文内容,下面案例可供参考 一、pandas是什么? 示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析... -
动态规划
2018-03-12 09:43:44一、动态规划概述 动态规划(Dynamic Programming)通常是用来解决最优化问题的。最初是由数学家在研究多阶段决策过程的优化问题时,提出的优化原理,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系... -
推导动态规划问题的公式
2021-10-17 19:57:04正式开始动态规划 先说说为什么是从动态规划开始 打开力扣刷题网站,选上动态规划标签。光是动态规划问题,就有350道。上边说了,目前力扣上一共也就又1900道。 所以如果把动态规划问题刷明白了,一下子就会了好多... -
五大经典算法-动态规划 及其算法应用
2021-07-11 10:39:12整篇文章分析整个动态规划算法,什么是动态规划,及动态规划算法在字符串匹配中使用、分治法的差别点、动态规划优点; -
什么是动态规划算法,常见的动态规划问题分析与求解
2015-04-27 23:09:04理解动态规划 动态规划中递推式的求解方法不是动态规划的本质。 我曾经作为省队成员参加过NOI,保送之后也给学校参加NOIP的同学多次讲过动态规划,我试着讲一下我理解的动态规划,争取深入浅出。希望你看了我的答案... -
算法导论-----动态规划是什么
2016-12-14 21:41:20本文更像是一篇科普,方便理解什么是动态规划。一、动态规划概述 动态规划(Dynamic Programming)通常是用来解决最优化问题的。最初是由数学家在研究多阶段决策过程的优化问题时,提出的优化原理,把多阶段过程... -
贪心算法与动态规划
2022-01-30 14:30:36二、原理拆解 1.根据当前情况做出下一步的最佳选择 2.做出选择后不反悔(区别于回溯算法) 3.用局部最优解逐步得到整体最优解 三、典型例题 1.背包问题 分析: 学习产出: 本篇博客学习自B站万诺coding ... -
【继动态规划后&计划】回溯算法和动态规划的区别与转换
2021-03-09 23:11:16动态规划几篇文章已经完成,接下来看 优势、什么时候用…… 我们前文经常说回溯算法和递归算法有点类似,有的问题如果实在想不出状态转移方程,尝试用回溯算法暴力解决也是一个聪明的策略,总比写不出来解法强。 ...