Coin Change 2

Medium

Python

def change(amount,coins):
    dp=[0]*(amount+1); dp[0]=1
    for coin in coins:
        for i in range(coin,amount+1):
            dp[i]+=dp[i-coin]
    return dp[amount]

Java

public int change(int amount,int[] coins){
    int[] dp=new int[amount+1]; dp[0]=1;
    for(int coin:coins)
        for(int i=coin;i<=amount;i++)
            dp[i]+=dp[i-coin];
    return dp[amount];
}

Key Insight

Combination count DP. Outer loop over coins prevents duplicates. Nearly identical.

Python → Java Differences

[0]*(n+1) vs new int[n+1]
Combination DP nearly identical
int array defaults to 0 Java

Python

def change(amount,coins):
    dp=[0]*(amount+1); dp[0]=1
    for coin in coins:
        for i in range(coin,amount+1):
            dp[i]+=dp[i-coin]
    return dp[amount]

Java

public int change(int amount,int[] coins){
    int[] dp=new int[amount+1]; dp[0]=1;
    for(int coin:coins)
        for(int i=coin;i<=amount;i++)
            dp[i]+=dp[i-coin];
    return dp[amount];
}

Algorithm Steps

1. dp[0]=1 base case
2. For each coin update

← Previous All Dynamic Programming Next →