Atinesh - 1 year ago 90
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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download