阅读 699

这都还不懂动态规划,那就没辙了

有一定规律可循,找套路.


什么是动态规划.

有多少种方式走到右下角(这才可以用动态规划) 输出所有走到右下角的路径(dfs 递归)


题目分类:

  1. 计数 有多少种方式走到右下角 有多少种方法选出K个数使得和是sum
  2. 求最大最小值 从左下角走到右下角路径的最大数值和 最长上升子序列长度
  3. 求存在性 取石子游戏,先手是否必赢 能不能选出K个数使得和是Sum


coin change

有3中硬币,面值:2元,5元,7元,每种硬币足够多

买一本书需要27元.

如何用最少的硬币组合正好付清,不需要对方找钱.(求最大最小值)

先不考虑动态规划: 直觉: 尽量用大的硬币,最后如果可以用一种硬币付清就行.

用直觉的答案是错误的.

动态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

递归解法:

递归算法分析:

现象:

  • f(20) 重复算了3次
  • f(15) 重复算了2次

结果:

冗余重复计算做了很多,效率低下.

如何避免?

  1. 将计算结果保存下来
  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

总结:

  1. 求最值类型优先考虑动态规划.
  2. 确定状态
    • 最后一步: 最优策略中使用的最后一枚硬币ak
    • 转化成子问题:最少的硬币拼出更小面值27-ak
  3. 确定转移方程:f[X] = min{f[X-2]+1,f[X-5]+1,f[X-7]+1} +1
  4. 确定初始条件 和边界情况: f[0]=0;无法拼出,F[X] = 正无穷
  5. 确定计算顺序: f[0]-->f[1]-->f[2]....

我的滴滴云专属AI大师码:3388, 购买滴滴云GPU等AI产品输入大师码享9折优惠。 点击 www.didiyun.com前往滴滴云官网购买

本篇文章由一文多发平台ArtiPub自动发布

关注下面的标签,发现更多相似文章
评论