322. Coin Change

solution322.py

# https://leetcode.com/problems/coin-change/description/

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return amount
        if not coins:
            return -1
        if amount in coins:
            return 1
        
        wallet = [-1] * amount
        w_ptr = 0
        
        for coin in coins:
            zero_indexed_coin = coin - 1
            if zero_indexed_coin < len(wallet):
                wallet[zero_indexed_coin] = 1
                
        while w_ptr < amount:
            if wallet[w_ptr] == -1:
                options = []
                for coin in coins:
                    w_val = w_ptr - coin
                    if w_val >= 0 and wallet[w_val] > 0:
                        options.append(wallet[w_val])

                min_option = -1

                if options:
                    min_option = min(options)
                if min_option > 0:
                    wallet[w_ptr] = min_option + 1

            w_ptr += 1
        return wallet[-1]