零钱兑换问题
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]
最后
以上就是优雅鸡最近收集整理的关于DP之零钱兑换问题零钱兑换问题的全部内容，更多相关DP之零钱兑换问题零钱兑换问题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复