1 min read

The Coin Change Problem

The coin change problem is a classic dynamic programming problem (unbounded knapsack problem) which can be solved recursively.

N = Coins with different denominations
D = Array of denominations
S = Total amount to make
C = Number of Combinations

Recursive Formula:
C(N, S) = C(N - 1, S) + C(N, S - D[N]);