Simple DP python solution using O(N) space and runtime of O(MN)


  • 0
    A
    class Solution(object):
        def change(self, amount, coins):
            """
            :type amount: int
            :type coins: List[int]
            :rtype: int
            """
            dp = [0 for _ in range(amount + 1)]
            dp[0] = 1 #initalize base case to 1 because this can always be reached
            for i in range(len(coins)):
                curr_coin = coins[i]
                for j in range(amount + 1):
                    #add current position and the current coin
                    new_amount = j + curr_coin
                    #do nothing if over the target or this index wasn't visited before
                    if new_amount > amount or dp[j] == 0: continue
                    #otherwise, add what's at the current index to the new index
                    dp[new_amount] += dp[j]
            return dp[amount]
    

Log in to reply
 

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