Coin Change —LeetCode 322

Difficulty: Medium; Category: Dynamic Programming

Coin Change - LeetCode

Creating a DP array mainly records the minimum number of coins for each amount.

Take Example 1 as an example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

The DP array would look like this:

• when amount is equal to 0, the coin we need is 0
  -> dp[0] == 0
• when amount is equal to 1, we use one of 1
  -> dp[1] = 1
• when amount is equal to 11, we use two of 5 and one of 1
  -> dp[11] = 3

Solution

class Solution:
    def coin_change(self, coins, amount):
        dp = [float('inf') for _ in range(amount+1)]
        dp[0] = 0
        for i in range(len(dp)):
            for c in coins:
                if i-c >= 0:
                    dp[i] = min(dp[i], dp[i-c]+1)
    return -1 if dp[-1] == float('inf') else dp[-1]

1. use float(‘inf’) for initializing the DP array, once the number of coins is smaller than float(‘inf’), it records the result into DParray
2. length of DP is amount+1 due to we start from 0 to the amount
3. dp[0] = 0 because when amount = 0, we don’t need any of coin
4. if i-c > = 0, it means we can use coin c for the current amount i
5. find the minimum number of coins between the current value in dp[i] dp[i]and the number of coins if we use c dp[i-c]+1.
   Why dp[i-c] + 1:
   when using c, the total number of coins is the sum of
   dp[i-c]: the minimum number of coins for the remaining amount, and
   +1: one of c we use
6. return value: if the answer is float(‘inf’) means there is no coin that fits the amount, so return -1

REFERENCE
https://www.youtube.com/watch?v=4S5x4SF4fsM