Atinesh - 1 year ago 64

Python Question

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`

Answer Source

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.