Very Simple Python Program with dynamic programming - 6 lines


  • 0
    W

    Here are the steps:

    1. Initialize a MAX and a dp list of size (amount + 1) initialized to 0s.
    2. For each i in range(1, amount + 1):
      dp = 1 + min([dp[i - coin] for coin in coins if i - coin >= 0])
    3. return dp[-1]
    def coin_change(coins, amount):
        MAX = 10 ** 5
        dp = [0] * (amount + 1)
        for i in range(1, amount + 1):
            coin_change_list = [dp[i - coin] for coin in coins if i - coin >= 0]
            dp[i] = 1 + min(coin_change_list) if coin_change_list else MAX
        return dp[-1] if dp[-1] < MAX else -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.