Atinesh Atinesh - 5 months ago 19
Python Question

Dynamic Programming Pr0blem on coins

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.


My code

def coins(n):
if (n < 0):
return 0
elif (n == 0):
return 1
else:
if (cnt_lst[n-1] == 0):
cnt_lst[n-1] = coins(n-1) + coins(n-5)
return cnt_lst[n-1]

if __name__ == "__main__":
cnt = int(input())
cnt_lst = [0] * cnt #Memiozation
ret = coins(cnt)
print(ret)


Above appraoch counting repeated patterns more than one (obviously I'm not checking them explicitly).


[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc


Maintaining another list which holds the previously seen patterns will require a lot of memory as
n
grows. What another approach we can use to overcome this problem.

Answer

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.

Let's say 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 0 through j.

We know that for any j, A[0][j] = 1 because there is exactly one way to represent the value 0: no coins.

Now suppose we want to find A[8][1], 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[8][0] ways to do this. If we do use a nickel then we have 3 cents left so there are A[3][1] ways to do this.

To compute A[8][0] we only have one coin available so A[8][0] = A[7][0] = ... = A[0][0] = 1.

To compute A[3][1] we can't use a nickel since 3 < 5, so A[3][1] = A[3][0]. From there we have A[3][0] = A[2][0] = ... = 1 as above.

In general:

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.