notes.html

problem 31 · 62 lines

<article>
<h3>Problem Analysis</h3>
<p>
This is a coin-change counting problem, a concrete instance of the broader
<a class="reference-source" href="https://en.wikipedia.org/wiki/Partition_(number_theory)" rel="noopener noreferrer" target="_blank">integer partition</a>
family: in how many distinct ways can a target amount be written as a sum of values drawn from a
fixed set of denominations? The decisive subtlety is that <em>order does not matter</em>. Spending
a 50p coin and then a 20p coin is the same combination as spending the 20p first and the 50p
second. We count unordered multisets of coins, not ordered sequences. Formally, we want the number
of non-negative integer solutions to <code>a1*c1 + a2*c2 + ... + ak*ck = T</code>, where each
<code>ci</code> is a denomination and each <code>ai</code> is how many of that coin we use.
</p>
<p>
The clean way to count these is
<a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
(DP) - a technique that builds the answer to a large problem from the cached answers to overlapping
smaller subproblems, so each subproblem is solved only once. This particular variant is the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem" rel="noopener noreferrer" target="_blank">unbounded knapsack</a>
pattern, "unbounded" because every coin may be reused without limit. I define <code>dp[i]</code> as
the number of ways to form amount <code>i</code> using the coins considered so far, with the base
case <code>dp[0] = 1</code> - there is exactly one way to make zero, namely by taking no coins.
The complexity is O(N * T) time and O(T) space, where N is the number of denominations and T is the
target. The single most important observation - the one that makes the count correct - is the loop
order: coins in the outer loop, amounts in the inner loop, which guarantees we count combinations
rather than permutations.
</p>
<h3>Solution Approach</h3>
<h4>Bottom-up Unbounded Knapsack DP</h4>
<p>
Both the Python and C files implement the identical algorithm. I allocate a 1D array
<code>dp</code> (called <code>result</code> in Python) of length <code>target_amount + 1</code>,
fill it with zeros, and set <code>dp[0] = 1</code>. I then loop over each coin denomination. For
each coin I sweep the amount index <code>i</code> upward from <code>coin</code> to
<code>target_amount</code>, applying the recurrence <code>dp[i] += dp[i - coin]</code>. After every
coin has been processed, <code>dp[target_amount]</code> holds the answer.
</p>
<p>
The recurrence reads as: "the number of ways to make amount <code>i</code> that use at least one of
the current coin equals the number of ways to make <code>i - coin</code>, to which we then add one
more of this coin." Because the inner loop runs <em>upward</em>, by the time I reach index
<code>i</code> the cell <code>dp[i - coin]</code> has already absorbed multiple uses of the current
coin within this same pass - this is precisely what makes the coin unbounded.
</p>
<p>
The reason the outer/inner ordering matters is a correctness issue, not a performance one. By
fixing a coin in the outer loop, I ensure that every count accumulated in <code>dp[i]</code> was
built using only the coins processed so far, in a fixed order. That enforces the invariant that I
never count two different orderings of the same multiset. Were I to swap the loops - amounts
outer, coins inner - I would instead count ordered sequences (permutations), a different and far
larger number.
</p>
<p>
The two language versions diverge only in arithmetic. For <code>target_amount = 100000</code> the
answer is <code>10056050940818192726001</code>, a 23-digit number near 10^22, which overflows a
64-bit integer (whose maximum is about 1.8 x 10^19). In Python this is a non-issue: its integers
are arbitrary precision and grow automatically. In C I use the GCC built-in <code>__int128</code>
for each <code>dp</code> cell, since 128 bits comfortably holds a 23-digit value. Because
<code>printf</code> has no format specifier for <code>__int128</code>, I wrote a small
<code>int128_to_str</code> helper that extracts decimal digits by repeated division by ten.
</p>
</article>