昨天做的字节跳动那一题比较简单, 直接采用贪心算法直接就能求解, 但是我最近看到一篇介绍动态规划的博文, 发现这种题目并没有那么简单, 只是刚好那一题用贪心算法直接求解即可.
题目: 某国有四种货币面值 1 元 面值 4 元 面值 8 元 面值 16 这四种. 小明有 W 元问如果把 W 元换成这几种货币, 最少需要多少张?
代码:
- def f(n):
- Sum = 0
- while n> 0:
- if n - 16>= 0:
- n -= 16
- Sum += 1
- elif n - 8>= 0:
- n -= 8
- Sum += 1
- elif n - 4>= 0:
- n -= 4
- Sum += 1
- elif n - 1>= 0:
- n -= 1
- Sum += 1
- return Sum
当然能用这种方法肯定特别简单, 但是如果我们把面值换一下, 比如 1 , 5, 11
如果有 15 元钱 用贪心算法肯定先换一张 11 元剩下四元只能用一元的来交换, 然后答案是最少 5 张, 可是如果我们用五元钱来交换很明显只要用三张. 所以在这样的情况下贪心算法肯定不合适了. 接下来我们来分析一下这几种情况假设, 你有十五元钱你该如何兑换呢和明显刚开始就三种情况, 我第一张兑换 11 元 然后就变成了
f(15-11) + 1 = f(4) + 1
, 这里加 1 的意思是我们兑换了一张十一元纸币.
第二种情况
f(15-5) + 1 = f(10) + 1
第三种情况:
f(15-1) + 1 = f(14) + 1
很明显我们要去的就是 min(f(4), f(10), f(f14)) + 1
于是我们就可以得出 f(n) = min(f(n-11), f(n-5), f(n-1)) + 1 我自己感觉动态规划的关键是找到递推式, 然后我们从小到大计算. 这样我们就可以得出代码了:
- def f(n):
- #递归出口
- if n == 0:
- return 0
- #我们首先假设需要兑换 n 张
- Sum = n
- #经过这几个 if 我们就更新出了在这三种情况中最小的 Sum
- #这几个值排列也有关系 我们把减一放在最上面减 11 放在最下面因为减一所产生的 sum 值最大
- if n - 1>= 0:
- #注意这个 + 1 是放在 min 的括号里面
- Sum = min(Sum, f(n-1) + 1)
- if n - 5>= 0:
- Sum = min(Sum, f(n-5) + 1)
- if n - 11>= 0:
- Sum = min(Sum, f(n-11) + 1)
- return Sum
- if __name__ == "__main__":
- n = 50
- for i in range(n):
- print('f({})= {}'.format(i, f(i)))
你以为到这就完了吗, 当然不是如果你运行一下代码就会发现 n 到五十几就需要好几秒, 因为我们没求出一个 n 时, 都是从 n=1 开始的, 我们还可以继续改进, 很简单的用空间换时间, 我们取一个字典存我们每一次计算的值这样就不会重复计算了.
- s = {}
- def f(n):
- global s
- #递归出口
- if n == 0:
- return 0
- #我们首先假设需要兑换 n 张
- Sum = n
- #经过这几个 if 我们就更新出了在这三种情况中最小的 Sum
- #这几个值排列也有关系 我们把减一放在最上面减 11 放在最下面因为减一所产生的 sum 值最大
- if n - 1>= 0:
- t = s.get('f({})'.format(n-1))
- if t is not None:
- Sum = min(Sum, t + 1)
- else:
- #注意这个 + 1 是放在 min 的括号里面
- Sum = min(Sum, f(n-1) + 1)
- if n - 5>= 0:
- t = s.get('f({})'.format(n-5))
- if t is not None:
- Sum = min(Sum, t + 1)
- else:
- Sum = min(Sum, f(n-5) + 1)
- if n - 11>= 0:
- t = s.get('f({})'.format(n-11))
- if t is not None:
- Sum = min(Sum, t + 1)
- else:
- Sum = min(Sum, f(n-11) + 1)
- s['f({})'.format(n)] = Sum
- return Sum
- if __name__ == "__main__":
- n = 50
- for i in range(n):
- print('f({})= {}'.format(i, f(i)))
来源: http://www.bubuko.com/infodetail-2990239.html