Ph.D. Qual Study Assistant

Coin Change Problem

1. The Problem

Given a set of coin denominations (e.g., 1, 5, 10, 25 cents) and a target amount `N`, find the minimum number of coins required to make change for `N`. We can assume an infinite supply of each coin denomination.

2. The Idea: Dynamic Programming

This is a classic optimization problem that can be solved efficiently using dynamic programming. The principle of optimality applies: an optimal solution for an amount `N` can be constructed from optimal solutions for amounts smaller than `N`.

Let `dp[i]` be the minimum number of coins required to make change for an amount `i`. Our goal is to find `dp[N]`.

  • Base Case: To make change for 0 cents, we need 0 coins. So, `dp[0] = 0`.
  • Recurrence Relation: To compute `dp[i]`, we consider each available coin denomination `c`. If we use a coin `c`, the remaining amount is `i - c`. The number of coins used would be `1 + dp[i - c]`. We want to choose the coin `c` that minimizes this value. We must check this for all coins `c` where `c <= i`.
dp[i] = 1 + min(dp[i - c]) for all coins c ≤ i

3. The Algorithm

  1. Let the set of coin denominations be `C = {c_1, c_2, ..., c_k}`. In this problem, `C = {1, 5, 10, 25}`.
  2. Create a 1D array, `dp`, of size `N+1` to store the minimum coins for each amount from 0 to N.
  3. Initialize `dp[0] = 0` and all other entries `dp[i]` to infinity.
  4. Iterate with `i` from 1 to `N`:
    • For each coin `c` in `C`:
      • If `i >= c`, it's possible to use this coin.
      • Update the minimum for `dp[i]`: `dp[i] = min(dp[i], 1 + dp[i-c])`.
  5. The final answer is `dp[N]`. If `dp[N]` is still infinity, it means `N` cannot be formed by the given coins.

4. Complexity Analysis

Time Complexity: O(N * k)
Where `N` is the target amount and `k` is the number of coin denominations. The algorithm has two nested loops: the outer loop runs `N` times, and the inner loop runs `k` times. Since `k` is a fixed constant (4 in this case), the complexity is effectively linear in `N`, i.e., O(N).
Space Complexity: O(N)
We use a 1D array `dp` of size `N+1` to store the intermediate solutions, which requires O(N) space.

Algorithm Visualization