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

什么是动态规划.

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

题目分类:

1. 计数
   有多少种方式走到右下角

有多少种方法选出 K 个数使得和是 sum

1. 求最大最小值

从左下角走到右下角路径的最大数值和
最长上升子序列长度

1. 求存在性

取石子游戏, 先手是否必赢
能不能选出 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 次

结果:

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

如何避免?

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 自动发布