← Dynamic Programming

Coin Change

Medium
Python
def coin_change(coins,amount):
    dp=[float('inf')]*(amount+1); dp[0]=0
    for coin in coins:
        for i in range(coin,amount+1):
            dp[i]=min(dp[i],dp[i-coin]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1
Java
public int coinChange(int[] coins,int amount){
    int[] dp=new int[amount+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0]=0;
    for(int coin:coins)
        for(int i=coin;i<=amount;i++)
            if(dp[i-coin]!=Integer.MAX_VALUE)
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
    return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}

Key Insight

float('inf') vs Integer.MAX_VALUE. Must guard against overflow when adding 1 in Java.

Python → Java Differences

  • float('inf') vs Integer.MAX_VALUE
  • min() vs Math.min()
  • Must guard overflow in Java
Python
def coin_change(coins,amount):
    dp=[float('inf')]*(amount+1); dp[0]=0
    for coin in coins:
        for i in range(coin,amount+1):
            dp[i]=min(dp[i],dp[i-coin]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1
Java
public int coinChange(int[] coins,int amount){
    int[] dp=new int[amount+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0]=0;
    for(int coin:coins)
        for(int i=coin;i<=amount;i++)
            if(dp[i-coin]!=Integer.MAX_VALUE)
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
    return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}

Algorithm Steps

1. Initialize with infinity
2. For each coin update amounts
3. Return result or -1
← Previous All Dynamic Programming Next →