DP 20. Minimum Coins | DP on Subsequences | Infinite Supplies Pattern

This chapter explores the Minimum Coins problem, a classic variation of Dynamic Programming on Subsequences featuring infinite supplies of coin denominations. We examine why the intuitive Greedy algorithm fails for arbitrary coin systems, build the complete recursive mental model (Pick and Non-Pick with multiple uses), optimize via Memoization and Tabulation, and finally achieve optimal Space Optimization.

1. Problem Statement & The Status Quo

The Core Objective

Given an array of coin denominations (e.g., [1, 2, 3]) and a target sum (e.g., target = 7), find the minimum number of coins required to exactly form the target sum. You have an infinite supply of each coin denomination, meaning any coin can be used zero, one, multiple, or infinitely many times as long as the sum equals the target.

Example Walkthrough

• Denominations: [1, 2, 3]
• Target: 7
• Valid Combinations:
  • 3 + 3 + 1 = 7 (Total coins used: 3)
  • 2 + 2 + 2 + 1 = 7 (Total coins used: 4)
  • 1 + 1 + ... + 1 = 7 (Total coins used: 7)
• Expected Output: 3 (the minimum coin count).

2. Why the Greedy Approach Fails

A natural first instinct is to use a Greedy strategy—always picking the largest possible coin denomination that fits into the remaining target, repeating until the target is met.

Where Greedy Works

If denominations are [1, 2, 3] and target is 7:

1. Pick largest coin $\le 7 \rightarrow 3$ (Remainder: $4$)
2. Pick largest coin $\le 4 \rightarrow 3$ (Remainder: $1$)
3. Pick largest coin $\le 1 \rightarrow 1$ (Remainder: $0$)

• Total Coins: $3$ (Optimal!).

Where Greedy Fails (Lack of Uniformity)

Consider denominations [9, 6, 5, 1] and target 11.

• Greedy Execution:
  1. Largest coin $\le 11$ is 9. Pick one 9. Remainder = $2$.
  2. Next coins (6, 5) are too large for remainder 2.
  3. Pick coin 1 twice. Remainder = $0$.
  4. Total Greedy Coins: 3 (9 + 1 + 1).
• Optimal Execution:
  1. Pick 6 and 5. Sum = $11$.
  2. Total Optimal Coins: 2 (6 + 5).

Why Greedy Fails: Greedy fails because there is no uniformity in the differences between coin denominations. Picking the locally largest coin often traps us in sub-optimal paths where smaller subsequent coins cannot efficiently bridge the remaining target.

3. Core Mental Model: Try All Combinations

Since Greedy is unreliable, we must systematically explore all possible combinations of coin selections. Because this falls under DP on Subsequences, our foundational pattern is Pick and Non-Pick, adapted here for infinite supplies.

Real-Life Analogy: The Cash Register Drawer

Imagine standing in front of a cash register with infinite bills of various denominations ($1,$2, $5,$10). To pay an exact bill of $11 with the minimum number of bills, you cannot just grab the largest bill blindly. You must evaluate the total count of bills if you decide to use a$5 bill versus skipping it and trying smaller bills, ensuring every branch is explored.

4. Step-by-Step Recursive Definition & Recurrence

To define our recursive function f(index, target), we establish three core parameters:

1. Index: The current coin denomination index we are considering (n - 1 down to 0).
2. Target: The remaining value we need to form.
3. Return Value: The minimum number of coins required to form the target using coins from index 0 to index.

The Two Choices (Infinite Supply Twist)

Unlike standard knapsack or subsequence problems where picking an item forces an index decrement (index - 1), infinite supply changes the behavior:

• Non-Pick: We skip the current coin index entirely. We move to index - 1 with the same target.
• Pick: We take the coin at the current index (provided coins[index] <= target). Because we can reuse it, we stay at the same index (index), but we reduce our target by coins[index], and add 1 to our coin count.

                    f(index, target)
                       /          \
      (Skip/Non-Pick) /            \ (Take/Pick)
                     v              v
     f(index - 1, target)      1 + f(index, target - coins[index])
     (Moves to prev coin)      (Stays at same coin, target reduced)

Recurrence Relation Formulation

# 1. Non-Pick Case
not_take = 0 + f(index - 1, target)

# 2. Pick Case (Condition: coins[index] <= target)
take = INT_MAX
if coins[index] <= target:
    take = 1 + f(index, target - coins[index])

# 3. Combine
return min(not_take, take)

5. Base Cases & Handling Edge Conditions

When our recursion reaches index == 0, we are left with only a single coin denomination at the very beginning of the array.

Analyzing Index 0

Suppose index == 0 and our single coin is coins[0] = 6:

• If target = 12, we can use two coins: 12 / 6 = 2.
• If target = 7, 7 is not divisible by 6, so it's impossible to form the target using only 6. We must return a very large number (1e9) to signal an invalid path.

if index == 0:
    if target % coins[0] == 0:
        return target / coins[0]
    else:
        return 1e9  # Represents infinity / impossible path

Note on Overflow Safety: We use 1e9 instead of standard INT_MAX (2^31 - 1). When our recursive steps add 1 + f(...), adding 1 to INT_MAX causes integer overflow bugs. 1e9 is safely large enough to act as infinity without risking overflow.

6. Complete Recursive & Memoized Implementation

Recursive Code Structure

int f(int ind, int T, vector<int>& nums) {
    if (ind == 0) {
        if (T % nums[0] == 0) return T / nums[0];
        return 1e9;
    }
    
    int notTake = 0 + f(ind - 1, T, nums);
    int take = 1e9;
    if (nums[ind] <= T) {
        take = 1 + f(ind, T - nums[ind], nums);
    }
    
    return min(notTake, take);
}

Memoization Matrix (O(N * Target))

Because subproblems overlap heavily (different paths reaching the same index with the same remaining target), we memoize states using a 2D DP table of size [N][target + 1] initialized to -1`.

int f(int ind, int T, vector<int>& nums, vector<vector<int>>& dp) {
    if (ind == 0) {
        if (T % nums[0] == 0) return T / nums[0];
        return 1e9;
    }
    
    if (dp[ind][T] != -1) return dp[ind][T];
    
    int notTake = 0 + f(ind - 1, T, nums, dp);
    int take = 1e9;
    if (nums[ind] <= T) {
        take = 1 + f(ind, T - nums[ind], nums, dp);
    }
    
    return dp[ind][T] = min(notTake, take);
}

7. Tabulation (Bottom-Up DP)

To convert memoization into bottom-up tabulation:

1. Declare a DP table: vector<vector<int>> dp(n, vector<int>(target + 1, 0)).
2. Translate the base case (ind == 0) for all possible targets from 0 to target.
3. Run nested loops for ind (1 to n-1) and target (0 to target).
4. Copy the recurrence relation directly.

Tabulation Code

int minimumElements(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(target + 1, 0));
    
    // Base Case Initialization for index 0
    for (int t = 0; t <= target; t++) {
        if (t % nums[0] == 0) dp[0][t] = t / nums[0];
        else dp[0][t] = 1e9;
    }
    
    // Fill table bottom-up
    for (int ind = 1; ind < n; ind++) {
        for (int t = 0; t <= target; t++) {
            int notTake = dp[ind - 1][t];
            int take = 1e9;
            if (nums[ind] <= t) {
                take = 1 + dp[ind][t - nums[ind]]; // Notice staying on 'ind' for infinite supply
            }
            dp[ind][t] = min(notTake, take);
        }
    }
    
    int ans = dp[n - 1][target];
    if (ans >= 1e9) return -1;
    return ans;
}

8. Space Optimization

Notice that computing row ind only requires values from the current row ind (for take) and the immediate previous row ind - 1 (for notTake). We can optimize space from $O(N \times \text{target})$ down to $O(\text{target})$ using two 1D arrays: prev and curr.

Space-Optimized Implementation

int minimumElements(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> prev(target + 1, 0), curr(target + 1, 0);
    
    // Base Case
    for (int t = 0; t <= target; t++) {
        if (t % nums[0] == 0) prev[t] = t / nums[0];
        else prev[t] = 1e9;
    }
    
    for (int ind = 1; ind < n; ind++) {
        for (int t = 0; t <= target; t++) {
            int notTake = prev[t];
            int take = 1e9;
            if (nums[ind] <= t) {
                take = 1 + curr[t - nums[ind]]; // Uses curr because coin can be reused
            }
            curr[t] = min(notTake, take);
        }
        prev = curr;
    }
    
    int ans = prev[target];
    if (ans >= 1e9) return -1;
    return ans;
}

9. Complexity Analysis Summary

10. Summary and Key Takeaways

• Subsequence Pattern: This problem extends the standard subsequence framework by introducing infinite supplies of items.
• Why Greedy Fails: Arbitrary coin systems lack uniformity in denomination differences, making greedy choices locally optimal but globally flawed.
• The Take Rule: When an item has infinite supply, do not decrement the index upon taking it; stay at the same index (ind) and reduce the target (target - coins[ind]).
• Safety Constants: Always use a safe infinity sentinel like 1e9 instead of INT_MAX to prevent integer overflow when adding 1 + f(...).
• Base Case Precision: Base cases at ind == 0 must check divisibility (target % nums[0] == 0) to determine if the target can be formed exclusively using the smallest coin.
• Space Reduction: Row dependency is restricted to the previous row (notTake) and current row (take), enabling $O(\text{target})$ space optimization.