Coin Change

Time

O (A \cdot k)

Space

O (A)

Problem

LeetCodeOpen original problem

You are given an integer array coins 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 may assume that you have an infinite number of each kind of coin.

Solution approach

Intuition

Let changes[i] be the fewest coins that make amount i. The last coin used for amount i is some coins[j], and the rest must be an optimal way to make i - coins[j]. So changes[i] is one more than the best changes[i - coins[j]]. Building the table from 0 upwards means every smaller amount is ready when it is needed.

Algorithm

Create changes of size amount + 1, filled with INT_MAX (unreachable), and set changes[0] = 0.
For every amount i from 1 to amount, and every coin coins[j] <= i, set changes[i] to the minimum of itself and changes[i - coins[j]] + 1.
If changes[amount] is still INT_MAX, return -1; otherwise return it.

The table uses long long, so adding 1 to INT_MAX cannot overflow, and an unreachable state stays above INT_MAX.

Complexity

Time: $O(A \cdot k)$ — for each of the $A$ = amount values, every one of the $k$ coins is tried.
Space: $O(A)$ — for the changes table.

Edge cases

amount = 0: returns 0, as no coins are needed.

Code

1
class Solution {
2
   public:
3
    int coinChange(vector<int>& coins, int amount) {
4
        vector<long long> changes(amount + 1, INT_MAX);
5
        changes[0] = 0;
6
        for (int i = 1; i <= amount; i++) {
7
            for (int j = 0; j < coins.size(); j++) {
8
                if (coins[j] <= i) {
9
                    changes[i] = min(changes[i], changes[i - coins[j]] + 1);
10
                }
11
            }
12
        }
13
        if (changes[amount] == INT_MAX) return -1;
14
        return changes[amount];
15
    }
16
};

Give it a try first

Attempt the problem on LeetCode — the code will still be here.