Find the number of ways to make n cents of change with (c1, ..., cn)-cent coins.

make_change.py

"""
Find the number of nonnegative integer solutions (x_1, ..., x_n)
to the equation a_1*x_1 + ...+ a_k*x_k = n,
where each a_i and n are positive integers.

Example: to find the number of ways to make $10.00 out of
1-, 5-, 10-, and 25-cent coins:

    >>> change(1000, (1, 5, 10, 25))
    142511
"""

# The algorithm starts with this idea:
#
# (# of ways to make 43 with 1s, 5s, and 10s)
#     ==  (# of ways to make 43 with 1s and 5s) +
#         (# of ways to make 33 with 1s, 5s, and 10s)
#
# This lets us fill out a dynamic programming table like this,
# one row at a time, left-to-right within each row:
#
# cents:            |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
# ------------------+------------------------------------------------
# using:{}          |  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
# using:{1}         |  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
# using:{1,5}       |  1  1  1  1  1  2  2  2  2  2  3  3  3  3  3  4
# using:{1,5,10}    |  1  1  1  1  1  2  2  2  2  2  4  4  4  4  4  6
#
# To compute a cell, add the number *above* the desired cell to the
# number *C entries to the left* of the desired cell, where C is the
# value of the coin that the row is adding, and assuming entries to
# the left of the table are zero.
#
# Since we're never looking backward in the previous row, only
# backward in the new row, we don't actually need to store the
# previous row, and we can instead operate in place.
#
# The runtime of this is O(n * len(coins)).

def change(n, coins):
    row = [1] + [0] * n
    for c in coins:
        for i in range(c, n + 1):
            row[i] += row[i-c]
    return row[-1]

if __name__ == "__main__":
    ways = change(1000, (1,5,10,25)) 
    print(f"You can make $10.00 of change in {ways} ways.")