Coin Change — Unbounded Knapsack DP

Problem

Given coins of different denominations and an amount, find minimum number of coins. Return -1 if impossible.

Example: coins=[1,5,6,9], amount=11 → 2 (5+6)

Approach — Bottom-Up DP

dp[0]=0, dp[i] = min(dp[i-c]+1 for c in coins if c<=i). Fill 1..amount.

Time: O(amount * len(coins)) | Space: O(amount)

Solutions

C

int coinChange(int* coins, int n, int amount) {
    int* dp=malloc((amount+1)*sizeof(int));
    for(int i=1;i<=amount;i++) dp[i]=amount+1;
    dp[0]=0;
    for(int i=1;i<=amount;i++)
        for(int j=0;j<n;j++)
            if(coins[j]<=i && dp[i-coins[j]]+1<dp[i]) dp[i]=dp[i-coins[j]]+1;
    int res=dp[amount]>amount?-1:dp[amount];
    free(dp); return res;
}

C++

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 c:coins) if(c<=i) dp[i]=min(dp[i],dp[i-c]+1);
        return dp[amount]>amount?-1:dp[amount];
    }
};

Java

class Solution {
    public int coinChange(int[] coins, int amount){
        int[] dp=new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0;
        for(int i=1;i<=amount;i++)
            for(int c:coins) if(c<=i) dp[i]=Math.min(dp[i],dp[i-c]+1);
        return dp[amount]>amount?-1:dp[amount];
    }
}

JavaScript

var coinChange = function(coins, amount) {
    const dp=new Array(amount+1).fill(amount+1); dp[0]=0;
    for(let i=1;i<=amount;i++)
        for(const c of coins) if(c<=i) dp[i]=Math.min(dp[i],dp[i-c]+1);
    return dp[amount]>amount?-1:dp[amount];
};

Python

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp=[float('inf')]*(amount+1); dp[0]=0
        for i in range(1,amount+1):
            for c in coins:
                if c<=i: dp[i]=min(dp[i],dp[i-c]+1)
        return dp[amount] if dp[amount]!=float('inf') else -1

Complexity

Time: O(amount * n) | Space: O(amount)