Leetcode 322. Coin Change

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Version 1

class Solution:def coinChange(self, coins, amount):if amount == 0:return 0stat = [0] * (amount + 1)for i in range(amount + 1):for coin in coins:if i - coin > 0 and stat[i - coin] > 0:if stat[i] > 0:stat[i] = min(1 + stat[i - coin], stat[i])else:stat[i] = 1 + stat[i - coin]elif i - coin == 0:stat[i] = 1return stat[amount] if stat[amount] > 0 else -1

• Version 2

class Solution:def coinChange(self, coins, amount):if amount == 0:return 0stat = [0 if i not in coins else 1 for i in range(amount + 1)]for i in range(amount + 1):for coin in coins:if i - coin > 0 and stat[i - coin] > 0:if stat[i] > 0:stat[i] = min(1 + stat[i - coin], stat[i])else:stat[i] = 1 + stat[i - coin]return stat[amount] if stat[amount] > 0 else -1

Reference

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