322. 零钱兑换

322. 零钱兑换

https://leetcode-cn.com/problems/coin-change/

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

把这题当作dp题练习

# 定义dp[i]表示什么，表示可以凑成金额为i的最小次数
# coins=[1,2,5],amount=11
# dp[i]=min(dp[i-cost_j])
# 比如此次这个11，min(dp[11-1],dp[11-2],dp[11-5])+1
# 思路是什么？

def min_coins(coins: list[int], amount: int) -> int:
    dp = (amount + 1) * [-1]
    dp[0] = 0
    for i in range(1, amount + 1):
        ans = 0
        # 找到min(i-cost[j])+1
        for cost in coins:
            if i - cost < 0:  # 处理凑不足以及coins无序状态
                continue
            # 可能凑得齐 dp[i - cost] >= 0
            # dp[i - cost]>0,表示能够到达i,i - cost有效
            ans = (dp[i - cost] + 1 if dp[i - cost] >= 0 else -1)
            # ans 是正数，ans也有可能是-1.dp也有可能是正数，也有-1
            # 当都是正数，可以比较大小。
            # 当最新的大于0，而dp[i]==-1,则表示可以到达，则ans替换掉dp[i]
            # 当ans==-1，表示i-cost[j]不可到达。则不用跟新dp[i]
            if ans >= 0 and dp[i] >= 0:
                dp[i] = min(ans, dp[i])
            else:
                dp[i] = ans if ans >= 0 else dp[i]
    return dp[amount]


if __name__ == "__main__":
    coins = [1]
    amount = 1
    ans = min_coins(coins, amount)
    print(ans)