零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明: 你可以认为每种硬币的数量是无限的。
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [-1 for _ in range(amount+1)]
dp[0]=0
for i in range(len(coins)):
if coins[i]<amount+1:
dp[coins[i]] = 1
for i in range(1,amount+1):
temp = []
for v in coins:
if i-v>=0 and dp[i-v]!=-1:
temp.append(dp[i-v]+1)
dp[i] = min(temp) if temp!=[] else -1
return dp[amount]
if __name__ == "__main__":
s= Solution()
coins = [1, 2, 5]
amount = 11
# coins = [2]
# amount = 3
r= s.coinChange(coins, amount)
print(r)
零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
from typing import List
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0 for _ in range(amount+1)]
dp[0] = 1
for value in coins:
for i in range(amount+1):
if i-value>=0:
dp[i] +=dp[i-value]
return dp[amount]
网友评论