Consider a below problem
Given an infinite number of nickels(5 cents) and pennies(1 cent). Write a code to calculate a number of ways of representing n cents.
if (n < 0):
elif (n == 0):
if (cnt_lst[n-1] == 0):
cnt_lst[n-1] = coins(n-1) + coins(n-5)
if __name__ == "__main__":
cnt = int(input())
cnt_lst =  * cnt #Memiozation
ret = coins(cnt)
[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc
Instead of using a 1-dimensional list, you can use a 2-dimensional array where one dimension is the total, and the second dimension is the largest-value coin available.
C is your list of coin values in ascending order (in your example,
C = [1, 5]). Then let
A[i][j] be the number of ways to represent value
i with coins
We know that for any
A[j] = 1 because there is exactly one way to represent the value
0: no coins.
Now suppose we want to find
A, the number of ways to represents 8 cents with pennies and nickels. Each representation will either use a nickel or it won't. If we don't use a nickel then we can only use pennies, so there are
A ways to do this. If we do use a nickel then we have
3 cents left so there are
A ways to do this.
A we only have one coin available so
A = A = ... = A = 1.
A we can't use a nickel since
3 < 5, so
A = A. From there we have
A = A = ... = 1 as above.
A[i][j] = A[i][j-1] if i < C[j] else A[i][j-1] + A[i-C[j]][j]
This algorithm works for any set of coin values.