Problem description:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

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

Example 2:

1
2
Input: coins = [2], amount = 3
Output: -1

Solution:

Key idea is to come up with the dp array. The array contains the min number of coins to compose n amount of money.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # how to acheive least coins of amount x?
        # bottom-up dp, compose every number from 1~x
        # for each amount x, traverse the coins to find if adding a coins[i]
        # could use less coins to by adding coins[i]
        # dp[x] = min(dp[x], dp[x-coins[i]]+1)
        
        dp = [amount+1 for i in range(amount+1)]
        dp[0] = 0
        
        for x in range(1, len(dp)):
            for i in range(len(coins)):
                if coins[i] <= x:
                    dp[x] = min(dp[x], dp[x-coins[i]]+1)
        return dp[-1] if dp[-1] <= amount else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0]= 0;
        
        for(int i= 1; i<= amount; i++){
            for(int j= 0; j< coins.size(); j++){
                if(coins[j] <= i)
                    dp[i]= min(dp[i], dp[i-coins[j]]+1);
            }
        }
        
        return dp[amount] > amount ? -1: dp[amount];
    }
};

time complexity: $O()$
space complexity: $O()$
reference: