DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences

This chapter covers the classic Coin Change 2 problem, exploring how to find the total number of ways to form a target sum when given an infinite supply of each coin denomination. This serves as a foundational bridge into unbounded knapsack-style dynamic programming on subsequences.

1. Why Do We Need This? (Problem Statement & Status Quo)

In previous dynamic programming problems (such as standard subset sum or target sum problems), each array element or coin could typically be used only once.

However, in the Coin Change 2 problem, the rules change:

• You are given an array of coin denominations (e.g., [1, 2, 3]) and a target sum (e.g., 4).
• Any element can be used any number of times (an infinite supply model).
• The goal is to find the total number of unique ways to form the target sum.

For instance, with coins [1, 2, 3] and target 4, valid combinations include:

• 1 + 1 + 1 + 1 (four 1s)
• 1 + 1 + 2 (two 1s, one 2)
• 2 + 2 (two 2s)
• 1 + 3 (one 1, one 3)

Total valid ways = 4.

2. Core Mental Model & The Infinite Supply Rule

Real-Life Analogy: Vending Machine Change

Imagine standing in front of a cash register with unlimited coins of denominations $1, $2, and $3. If a customer needs $4 in change, you can hand over four $1 coins, two $2 coins, a $1 and a $3 coin, etc. Because your supply is infinite, handing over a coin does not permanently remove it from your available options for subsequent steps.

The Critical Transition Rule

• Single-Use Rule: When an element is used only once, a take decision forces the recursion to move to the previous index (index - 1).
• Infinite Supply Rule: When an element can be reused infinitely, a take decision allows you to stay at the same index (index), because that exact coin remains available for selection in the next step.

3. Naive vs. Better Approach: The Recursive Strategy

When counting total number of ways:

1. Base cases return 1 if a valid combination/destination is successfully achieved, and 0 otherwise.
2. At every state, we explore all possibilities (notTake and take).
3. We sum all valid possibilities and return the total count.

The Recurrence Relation

4. Step-by-Step Evolution of the Code

Step 1: Pure Recursion (Exponential Time)

long long f(int index, int target, vector<int>& arr) {
    // Base Case: When standing at the first index (index 0)
    if (index == 0) {
        return (target % arr[0] == 0) ? 1 : 0;
    }
    
    // Option 1: Not Take current coin
    long long notTake = f(index - 1, target, arr);
    
    // Option 2: Take current coin (if coin value <= target)
    long long take = 0;
    if (arr[index] <= target) {
        // STAY AT THE SAME INDEX because of infinite supply!
        take = f(index, target - arr[index], arr);
    }
    
    return notTake + take;
}

Step 2: Memoization (Top-Down DP)

To eliminate overlapping subproblems, we introduce a 2D DP table of size [N][Target + 1] initialized to -1.

long long f(int index, int target, vector<int>& arr, vector<vector<long long>>& dp) {
    if (index == 0) {
        return (target % arr[0] == 0) ? 1 : 0;
    }
    
    if (dp[index][target] != -1) return dp[index][target];
    
    long long notTake = f(index - 1, target, arr, dp);
    long long take = 0;
    if (arr[index] <= target) {
        take = f(index, target - arr[index], arr, dp); // Same index!
    }
    
    return dp[index][target] = notTake + take;
}

5. Tabulation Approach (Bottom-Up DP)

To convert the memoized solution into iterative tabulation:

1. Declare a 2D DP table: vector<vector<long long>> dp(n, vector<long long>(target + 1, 0)).
2. Initialize the base case for index = 0 across all possible target values.
3. Nested loops iterate through indices (1 to n-1) and targets (0 to target).

long long change(int target, vector<int>& arr) {
    int n = arr.size();
    vector<vector<long long>> dp(n, vector<long long>(target + 1, 0));
    
    // Base Case Initialization for Index 0
    for (int t = 0; t <= target; t++) {
        if (t % arr[0] == 0) dp[0][t] = 1;
    }
    
    // Fill DP table bottom-up
    for (int index = 1; index < n; index++) {
        for (int t = 0; t <= target; t++) {
            long long notTake = dp[index - 1][t];
            long long take = 0;
            if (arr[index] <= t) {
                // Notice we reference 'index' (current row) instead of 'index - 1' for take
                take = dp[index][t - arr[index]];
            }
            dp[index][t] = notTake + take;
        }
    }
    
    return dp[n - 1][target];
}

6. Space Optimization (Optimizing to 1D / Two Rows)

Because computing the current row (index) only requires values from the previous row (index - 1) and the current row itself (index), we can compress our memory footprint from O(N × Target) down to O(Target) using two 1D vectors (prev and curr).

long long change(int target, vector<int>& arr) {
    int n = arr.size();
    vector<long long> prev(target + 1, 0), curr(target + 1, 0);
    
    // Base Case Initialization
    for (int t = 0; t <= target; t++) {
        if (t % arr[0] == 0) prev[t] = 1;
    }
    
    // Iterating through indices
    for (int index = 1; index < n; index++) {
        for (int t = 0; t <= target; t++) {
            long long notTake = prev[t];
            long long take = 0;
            if (arr[index] <= t) {
                take = curr[t - arr[index]]; // Using curr row for infinite supply
            }
            curr[t] = notTake + take;
        }
        prev = curr; // Shift rows for next iteration
    }
    
    return prev[target];
}

7. Comparative Synthesis of Approaches

8. Summary and Key Takeaways

• Infinite Supply Rule: When items can be reused infinitely, taking an element keeps the recursion or tabulation state at the same index rather than decrementing to index - 1.
• Counting Ways Pattern: Base cases return 1 upon successful exact target matching, 0 otherwise, and intermediate steps sum all valid possibilities (notTake + take).
• Base Case Initialization: At index = 0, any target that is an exact multiple of arr[0] (target % arr[0] == 0) yields 1 valid way.
• Data Types Matter: Always use long long for coin change problems to prevent integer overflow during summation of large combination counts.
• Space Reduction: Tabulation states dependent only on the current row and previous row can be compressed into 1D rolling arrays.