Coin Change – LeetCode Solution [Medium]

Problem

You are given an integer vector (or array) coins[n] representing coins of different denominations and an integer amount representing a total amount of money. Return 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. You could assume to have an infinite number of each kind of coin.

LeetCode Problem Link

Input

int vector: coins[n], int: amount

Output

an integer representing fewest number of coins that you need to make up amount

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Sample Input

coins = [1,2,5], amount = 11

Sample Output

3

Explanation: 11 = 5 + 5 + 1

Solution

This problem could be solved in polynomial time using Dynamic programming.

Dynamic Programming

Optimal Substructure

An optimal solution to problem contain optimal solution to subproblems. To consider all kinds of coins, 2 cases for every coin arises:

1. coin[i] is included in the optimal set
2. coin[i] is not included in the optimal set

Therefore, minimum number of coins needed to make the given amount j is minimum of the following:

1. Minimum number of coins required to obtain amount (j) using coins[0..i]. (coin[i] is not included)
2. Minimum number of coins required to obtain amount (j – coins[i]) using coins[0..i] + 1. (coin[i] is included)

dp[j] represents the minimum number of coins that you need to make up amount j

Now according to optimal substructure:
for i = 0 to coins.size()-1:
  for j = coins[i] to amount:
    dp[j] = min (dp[j], dp[j-coins[i]]+1)

Base case & Initialisation

dp[0] = 0, minimum number of coins required to make sum = 0, is 0
dp[j] = INT_MAX, if j > 0

Code Implementation

int coinChange(vector<int>& coins, int amount) {
    int *dp = new int[amount+1]();
    
    dp[0] = 0;
    
    for (int i=1; i<=amount; i++) {
        //(- 1)To prevent Integer Overflow
        dp[i] = INT_MAX-1;
    }
    
    for (int i=0; i<coins.size(); i++) {
        for (int j=coins[i]; j<=amount; j++) {
            dp[j] = min (dp[j], dp[j-coins[i]]+1);
        }
    }
    
    return dp[amount] == INT_MAX-1 ? -1 : dp[amount];
}

Time complexity of the above solution is O(N*amount) (N is the size of coins vector) and auxiliary space required is O(amount).