DP之零钱兑换问题零钱兑换问题

119 阅读 0 评论 79 点赞

我是靠谱客的博主优雅鸡，这篇文章主要介绍DP之零钱兑换问题零钱兑换问题，现在分享给大家，希望可以做个参考。

零钱兑换问题

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def coinChange(coins, amount): # 给你的零钱面额(不限数量）
要凑的总面额
# 异常判断特殊情况（完全不可能有解的情况！）
if amount == 0:
return 0
if len(coins) == 0:
return -1
if len(coins) ==1 and
coins[0] > amount:
return -1
# 建立存储空间并初始化, 有的位置可能得不到
mem = [-1 for i in range(amount + 1)]
mem[0] = 0
for i in range(1, amount + 1):
cur_min = amount + 1
for c in coins:
# 当钱币面值 < 当前需要凑的金额时
if c <= i:
# 动态转移方程（找减少c元需要的最少零钱个数量，c为存在的零钱面额）
cur_min = mem[i - c] if mem[i - c] < cur_min else cur_min
# 不断更新为i元时，需要的最少零钱个数
mem[i] = cur_min + 1 if cur_min < amount + 1 else amount + 1
# 找不到这一方案！

if mem[-1] == amount + 1:
return -1
else:
return mem[-1]