题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
|
示例 2:
输入: coins = [2], amount = 3
输出: -1
|
分析
考虑状态方程，需描述出组合成总金额所花最少的硬币个数。
dp[i][j] = min(dp[i][j], dp[i-1][j-coin_i*k] + k)
= min(dp[i][j], dp[i][j-coin_i] + 1)
dp[j] = min(dp[j], dp[j-coin_i] + 1)
|
以*示例 1 *为例
code
DP
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount + 5)
dp[0] = 0
for coin in coins:
for i in range(amount+1):
if (i - coin >= 0):
dp[i] = min(dp[i], dp[i-coin] + 1)
return -1 if dp[amount] >= amount + 1 else dp[amount]
|
DFS + greedy + pruning
待补充
