Coin Change

Problem page:https://leetcode.com/problems/coin-change

Solution

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        min_coins = [amount + 1] * (amount + 1)
        min_coins[0] = 0

        for i in range(1, amount + 1):
            for c in coins:
                if i - c >= 0:
                    min_coins[i] = min(min_coins[i], 1 + min_coins[i - c])

        return min_coins[-1] if min_coins[-1] != amount + 1 else -1

Complexity

• time: O(n * m) n is the length of coins, m is amount
• space: O(m)