Problem Analysis
This is a coin-change counting problem, a concrete instance of the broader
integer partition
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 order does not matter. 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 a1*c1 + a2*c2 + ... + ak*ck = T, where each
ci is a denomination and each ai is how many of that coin we use.
The clean way to count these is
dynamic programming
(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
unbounded knapsack
pattern, "unbounded" because every coin may be reused without limit. I define dp[i] as
the number of ways to form amount i using the coins considered so far, with the base
case dp[0] = 1 - 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.
Solution Approach
Bottom-up Unbounded Knapsack DP
Both the Python and C files implement the identical algorithm. I allocate a 1D array
dp (called result in Python) of length target_amount + 1,
fill it with zeros, and set dp[0] = 1. I then loop over each coin denomination. For
each coin I sweep the amount index i upward from coin to
target_amount, applying the recurrence dp[i] += dp[i - coin]. After every
coin has been processed, dp[target_amount] holds the answer.
The recurrence reads as: "the number of ways to make amount i that use at least one of
the current coin equals the number of ways to make i - coin, to which we then add one
more of this coin." Because the inner loop runs upward, by the time I reach index
i the cell dp[i - coin] has already absorbed multiple uses of the current
coin within this same pass - this is precisely what makes the coin unbounded.
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 dp[i] 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.
The two language versions diverge only in arithmetic. For target_amount = 100000 the
answer is 10056050940818192726001, 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 __int128
for each dp cell, since 128 bits comfortably holds a 23-digit value. Because
printf has no format specifier for __int128, I wrote a small
int128_to_str helper that extracts decimal digits by repeated division by ten.