# given an amount and coin denominations,
# compute the number of ways to make amount with coins of the given denoms
# 4, [1,2,3] -> 4
def ways_to_make(amount, denoms):
    # ways to make 4
    # ~ ways(4 - 3) + ways(4 - 2) + ways(4 - 1) ~

    # ways(1, largest=1) + ways(2, largest=1)

    # dim 1: amount
    # dim 2: largest denomination used

    # 1: 1
    # 2: 11, 2
    # 3: 111, 12, 3
    # 4:

    #              amount
    #
    #            0 1 2 3 4
    #          1 1 1 1 1 1
    # largest  2 1 1 2 2 3
    #          3 1 1 2 3 4
    #          4 1 1 2 3 5

    # ways(4, 3) =
    #   # use 3
    #   ways(4 - 3, 3) = 1
    #   # use 2
    #   ways(4 - 2, 2) = 2
    #   # use 1
    #   ways(4 - 1, 1) = 1

    denoms.sort()

    # there's one way to make 0, no matter what denominations we use
    ways = [[1] * len(denoms)]

    # determine how many ways there are to make current_amount (using only
    # denominations or size `row` or smaller)
    for current_amount in range(1, amount + 1):

        column = []
        for row in denoms:
            count = 0

            # for each denomination less than or equal to the current row, add
            # the number of ways to make `current_amount - denom`.
            for denom_ix, denom in enumerate(denoms):
                # this and all larger denominations are too big
                if denom > row or denom > current_amount:
                    break
                else:
                    count += ways[current_amount - denom][denom_ix]

            column.append(count)

        ways.append(column)

    return ways[amount][-1]

if __name__ == '__main__':
    print(ways_to_make(0, [1]))
    print(ways_to_make(0, [1,2,3]))
    print(ways_to_make(4, [1,2,3]))
    print(ways_to_make(4, [1,2,3,7,8,9,1000]))
    print(ways_to_make(4, [1,2,3,4]))
    print(ways_to_make(4, list(range(1,100000))))