Coin Change

Intuition

Solution

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

        for i in range(1, amount+1):
            for c in coins:
                if i - c < 0:
                    break
                if ans[i - c] != -1:
                    if ans[i] == -1 or ans[i] - 1 > ans[i -c]:
                        ans[i] = ans[i-c] + 1
        # print(ans)
        return ans[-1]