[动态规划入门] 记录动态规划的学习!

dp与贪心

贪心是我们一开始就接触的算法, 又因为贪心和dp有关联所以这里先提贪心

经典例题1.

思路

如果你是新手的话 那么你可能会 按先用大的来凑 然后再用小的 没错这就是贪心了,顾名思义和你的想法差不多 贪心是一种 只考虑眼前情况 的策略 官方点的话是这样的 贪心算法在有最优子结构的问题中尤为有效

但是这题如果使用贪心是错的

我们考虑一组新的硬币面值：1,5,11.

于是有了一个反例： 如果我们要凑出15，

贪心策略是： 15 = 11+41,共用5枚硬币。 而最佳策略是： 15 = 35,共用3枚硬币。

/// 因此贪心策略就陷入了困境: 鼠目寸光 ///

那该怎么避免贪心的“鼠目寸光”呢？

我们重新分析刚刚的情况： w=15时，我们取了11，接下来面对w=4的情况。 w=15时，如果我们取5，接下来就面对w=10的情况。

我们记“凑出n需要用到的最少硬币数量”为f(n).

那么，如果我们取了11， 则： cost=f(4)+1=4+1=5. 解释： 我们用了一枚面值为11的硬币，所以加一； 接下来面对的是w=4的情况。 f(4)我告诉你等于4.

性质

我们注意到了一个很棒的性质： f(n)只与 f(n−1),f(n−5),f(n−11) 相关。 更确切地说： f(n)=min⁡{f(n−1),f(n−5),f(n−11)}+1

总结一下:

我们可以发现 我们的答案是递推一样的 直接就推出来了这就是dp了

dp的两个名词: 无后效性

一旦f(n)确定， “我们如何凑出f(n)”就再也用不着了。 要求出f(15)， 只需要知道f(14),f(10),f(4)的值， 而f(14),f(10),f(4)是如何算出来的， 对之后的问题没有影响。 “未来与过去无关”

最优子结构

f(n)的定义就已经蕴含了“最优”。 利用w=14,10,4的最优解， 我们即可算出w=15的最优解。

大问题的最优解可以由小问题的最优解推出， 这个性质叫做“最优子结构性质”。

Dp的一般思路:

• 看是否满足两个性质
• 将大问题转换成小问题
• 设计状态,考虑当前需要求出的是什么
• 设计转移方程