290 字
1 分钟
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
**输入：**coins = [1, 2, 5], amount = 11
输出：3
**解释：**11 = 5 + 5 + 1
写一下主要代码的思路，还是数组dp储存答案，用前面的答案计算后面的，使用循环计算所有值
dp[0]=0 ##也就是0元的时候需要0个硬币##双层循环for i in range(1,1+amount):##amount+1因为需要一直算到amount dp[i]=float('inf')##每次进循环前重置为无穷大，不然数组初始化全为0，取小只会取0 for j in range(len(coins)): if(coins[j]<i):##每次硬币数值必须小于钱数，不然减出来负数没意义 dp[i]=min(dp[i],dp[i-coins[j]]+1)if dp[amount]=='inf':##如果最后还是无穷大，返回-1，没有方案 return -1return dp[amount]感觉动态规划的都要好好复习一遍，还是挺有必要的