image
有一定规律可循,找套路.
什么是动态规划.
有多少种方式走到右下角(这才可以用动态规划)
输出所有走到右下角的路径(dfs 递归)
image
题目分类:
- 计数
有多少种方式走到右下角
有多少种方法选出K个数使得和是sum - 求最大最小值
从左下角走到右下角路径的最大数值和
最长上升子序列长度 - 求存在性
取石子游戏,先手是否必赢
能不能选出K个数使得和是Sum
image
coin change
image
有3中硬币,面值:2元,5元,7元,每种硬币足够多
买一本书需要27元.
如何用最少的硬币组合正好付清,不需要对方找钱.(求最大最小值)
先不考虑动态规划:
直觉:
尽量用大的硬币,最后如果可以用一种硬币付清就行.
image
用直觉的答案是错误的.
动态4步走:
1. 确定状态(定海神针)
-
解动态规划需要开一个数组,数组每个元素f[i]活着f[i][j] 代表什么
- 类似于解数学中,X,Y,Z代表什么(状态)
-
确定状态需要两个意思:
-
最后一步
- 虽然不知道最优策略是什么,但是最优策略肯定是K枚硬币a1,a2,....ak 面值加起来是27
- 所以一定有一枚最后硬币:ak
- 除掉这枚硬币,前面硬币的面值加起来是27-ak
- 我们不关心 K-1枚硬币是如何拼出27-ak的(可能是1种拼法,可能有100种拼法),而且我们现在甚至还不清楚ak和k,但是我们确定前面的硬币拼出了27-ak(最后一步,不确定中有确定的)
- 关键: 因为是最优策略,因为拼出27-ak的硬币数一定要最少,否则就不是最优策略了. 不考虑最后一枚硬币,剩下硬币的拼法也是最优策略.
-
子问题:
- 因而,最少用多少硬币可以拼出27-ak
- 原来的问题是用多少枚硬币拼出27
- 我们将原问题转换成子问题,而且规模更小: 27-ak
- 为了简化定义,我们设f(X)= 最少用多少枚硬币拼出X
即使分析了 最后一步,以及子问题,但仍然不知道最后一枚硬币 ak是多少
-
最后一枚硬币ak 只可能是2,5,7
- 如果ak=2,f(27)= 应该是f(27-2)+1
- 如果ak=5,f(27)= 应该是f(27-5)+1
- 如果ak=7,f(27)= 应该是f(27-7)+1
- 除此之外,没有其他可能了.
- 需要求最少的硬币数:
- f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1} +1
-
image
递归解法:
image
递归算法分析:
image
现象:
- f(20) 重复算了3次
- f(15) 重复算了2次
结果:
冗余重复计算做了很多,效率低下.
如何避免?
- 将计算结果保存下来
- 并改变计算的顺序.
2. 转移方程
- 设状态f[X] = 最少用多少枚硬币拼出X (方括号是表示数组)
- 对于任意X:
- 到这里,动态规划问题已经解决了一半.
image
3. 初始条件 和 边界问题
确定好转移方程后,需要确定初始条件和 边界问题.
- f[27] = min{f[27-2]+1,f[27-5]+1,f[27-7]+1} +1
- 两个问题: X-2,X-5, 或者 X-7 小于0 怎么办?什么时候停下来?
- 如果不能拼出Y,就定义f[Y]=正无穷
- 例如f[-1]=f[-2]=正无穷
- 在实际操作中,不会真的开f[-1]
- 所以 f[1]= min{f[-1]+1,f [-4]+1,f[-6]+1}= 正无穷,表示拼不出 1
- 初始条件: f[0] = 0
4. 确定计算顺序
- 初始条件: f[0]= 0
- 然后按递增顺序计算 f[1],f[2],f[3]....(一般都是递增计算)
- 好处: 但我们计算f[X]时,f[X-2],f[X-5],f[X-7]都已经得到结果了,避免了重复计算
image
时间复杂度:
O(n)= n
image
总结:
- 求最值类型优先考虑动态规划.
- 确定状态
- 最后一步: 最优策略中使用的最后一枚硬币ak
- 转化成子问题:最少的硬币拼出更小面值27-ak
- 确定转移方程:f[X] = min{f[X-2]+1,f[X-5]+1,f[X-7]+1} +1
- 确定初始条件 和边界情况: f[0]=0;无法拼出,F[X] = 正无穷
- 确定计算顺序: f[0]-->f[1]-->f[2]....
我的滴滴云专属AI大师码：3388，
购买滴滴云GPU等AI产品输入大师码享9折优惠。
点击 www.didiyun.com前往滴滴云官网购买
本篇文章由一文多发平台ArtiPub自动发布
