共计 1625 个字符，预计需要花费 5 分钟才能阅读完成。
有一定规律可循, 找套路.
什么是动态规划.
有多少种方式走到右下角 (这才可以用动态规划)
输出所有走到右下角的路径(dfs 递归)
题目分类:
- 计数
有多少种方式走到右下角
有多少种方法选出 K 个数使得和是 sum
- 求最大最小值
从左下角走到右下角路径的最大数值和
最长上升子序列长度
- 求存在性
取石子游戏, 先手是否必赢
能不能选出 K 个数使得和是 Sum
coin change
有 3 中硬币, 面值:2 元,5 元,7 元, 每种硬币足够多
买一本书需要 27 元.
如何用最少的硬币组合正好付清, 不需要对方找钱.(求最大最小值)
先不考虑动态规划:
直觉:
尽量用大的硬币, 最后如果可以用一种硬币付清就行.
用直觉的答案是错误的.
动态 4 步走:
1. 确定状态(定海神针)
解动态规划需要开一个数组, 数组每个元素 f[i]活着 fi 代表什么
- 类似于解数学中,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
递归解法:
递归算法分析:
现象:
- f(20) 重复算了 3 次
- f(15) 重复算了 2 次
结果:
冗余重复计算做了很多, 效率低下.
如何避免?
- 将计算结果保存下来
- 并改变计算的顺序.
2. 转移方程
- 设状态 f[X] = 最少用多少枚硬币拼出 X (方括号是表示数组)
- 对于任意 X:
- 到这里, 动态规划问题已经解决了一半.
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]都已经得到结果了,避免了重复计算
时间复杂度:
O(n)= n
总结:
- 求最值类型优先考虑动态规划.
确定状态
- 最后一步: 最优策略中使用的最后一枚硬币 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 自动发布
正文完
