Back to solutions

Coin Change

MediumDynamic Programming

Return the fewest number of coins needed to make a given amount, or -1 if it cannot be made.

Open problem
Constraints
  • 1 <= coins.length <= 12
  • 0 <= amount <= 10^4

Bottom-up unbounded knapsack

Time O(amount * coins)Space O(amount)

dp[a] is the fewest coins to make amount a. For each amount, try every coin and take one plus the best for the remainder. Initialize with infinity and dp[0] = 0.

#include <bits/stdc++.h>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}