Coin Change 2 [0/1 Knapsack Variation]

Nov 4


def change(amount, coins):
    # Initialize dp array with base case
    dp = [1] + [0] * amount
    
    # For each coin, calculate combinations for all amounts
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
            
    return dp[amount]


class Solution {
    // Modified 0/1 knapsack with item reuse
    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];
    }
}


class Solution {
public:
    int change(int amount, vector& coins) {
        // Initialize dp array with base case
        vector dp(amount + 1, 0);
        dp[0] = 1;
        
        for (int coin : coins)
            for (int i = coin; i <= amount; i++)
                dp[i] += dp[i - coin];
                
        return dp[amount];
    }
};

Problem Statement

You are given an integer array coins representing different denominations of coins and an integer amount representing a total amount of money. Return the number of different ways you can make amount by using the coins. You may use each coin an unlimited number of times.

Category: Dynamic Programming | Difficulty: Medium

Detailed Explanation

Approach

This problem is a variation of the unbounded knapsack problem, where we can reuse items infinitely. The key insight is that we can modify the traditional knapsack approach to handle the reuse of items by staying in the same row of our dynamic programming solution, which allows us to optimize it into a 1D array.

Key Concepts

Unbounded Knapsack: Unlike the traditional knapsack problem where we can use each item only once, this problem allows unlimited use of each coin. This fundamental difference changes how we structure our dynamic programming solution.
1D DP Array: The ability to reuse items allows us to optimize our space complexity by using a single array instead of a 2D matrix. This works because we only need to reference values we've already calculated in the current iteration.
Base Case: We set dp[0] = 1 because there is exactly one way to make amount 0 (by using no coins). This base case is crucial for building up our solution.

Algorithm Steps

Initialize our dp array with dp[0] = 1 and all other values as 0. The array size is amount + 1 to include the target amount.
For each coin denomination:
- We iterate through all amounts from the coin value up to the target amount
- For each amount, we add the number of ways we can make (current amount - coin value)
- This effectively counts all possible combinations using the current coin
The value in dp[amount] will represent all possible combinations to make the target amount.

Visual Example

coins = [1,2,5], amount = 5

dp array evolution:
[1,0,0,0,0,0]  Initial
[1,1,1,1,1,1]  After coin 1
[1,1,2,2,3,3]  After coin 2
[1,1,2,2,3,4]  After coin 5

Let's break down dp[5] = 4:
1. {1,1,1,1,1}
2. {1,1,1,2}
3. {1,2,2}
4. {5}

Time and Space Complexity

Time Complexity: O(amount * number of coins) - We need to process each coin for each possible amount
Space Complexity: O(amount) - We only need a single array of size amount + 1

Key Differences from Regular Knapsack

In a regular 0/1 knapsack problem, we would typically use dp[i-1][j] + dp[i-1][j-coin] because we can't reuse items. However, since we can reuse coins in this problem, we use dp[i][j-coin] instead, allowing us to consider the same coin multiple times. This difference is what allows us to optimize our space complexity to O(amount) instead of O(n * amount).

Edge Cases

amount = 0: Returns 1 (one way to make zero: use no coins)
empty coins array: Returns 0 (no ways to make any amount)
amount < smallest coin: Returns 0
single coin that divides amount perfectly: Returns 1

Tal Nabulsi