Leetcode 322.Coin Change[DP]

# dp[i][j] 表示使用前 i 种硬币表示总额 j 所用的最少硬币数
# 初始状态 dp[-1][j] = ∞  dp[i][0] = 0
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[i]，进一步压缩，使用滚动数组
dp[j] = min(dp[j], dp[j-coin_i] + 1)

# 执行用时：1672 ms，击败了 39.85% 的用户
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]