Can somebody tell me why I need these two solutions produce different results?
jiggly_puff
27

I came up with this solution:

    def change(self, amount, coins):
        dp = [0 for i in range(amount+1)]
        dp[0] = 1
        
		for i in range(amount+1):
			for coin in coins:
				if i - coin >= 0: 
					dp[i] += dp[i - coin]

        return dp[amount]

Where in fact this is the correct solution:

    def change(self, amount, coins):
        dp = [0 for i in range(amount+1)]
        dp[0] = 1
        
        for coin in coins:
            for i in range(amount+1):
				if i - coin >= 0: 
					dp[i] += dp[i - coin]

        return dp[amount]

Can someone explain to me me why it is incorrect to loop through the coins inside the main loop?

Comments (0)