Solution for 322 coin change problem.

322_Coin_Change.py

import typing
from typing import List 
import sys


class Solution:
    def __init__(self) -> None:
        self.amount_memorization = {}
    
    def coinChange(self, coins: List[int], amount: int) -> int:
        miniCount = self.coinChange__(coins, amount)
        
        if miniCount < sys.maxsize:
            return miniCount
        
        return -1
        
    def coinChange__(self, coins: List[int], amount: int) -> int:
        if self.amount_memorization.get(amount) != None:
            return self.amount_memorization[amount]
        
        if amount == 0:
            return 0
        
        miniStep = sys.maxsize
        idx = 0 
        while idx < len(coins):
            if amount >= coins[idx]:
                remainingAmount = amount - coins[idx]
                # print(f"amount: {amount}. remainingAmount: {remainingAmount}")
                currentStep = self.coinChange__(coins, remainingAmount)
                miniStep = min(currentStep + 1, miniStep)
                
            idx += 1
        
        if miniStep < sys.maxsize:
            
            self.amount_memorization[amount] = miniStep
            return miniStep
        
        self.amount_memorization[amount] = sys.maxsize
        return sys.maxsize