Geek Answers Handbook

Dynamic Coin Programming

Consider the task below

Given the infinite amount of nickels (5 cents) and pennies (1 cents). Write code to calculate several ways to represent 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)

The above counter repeats several patterns of more than one (obviously, I am not checking them explicitly).

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

Maintaining another list that contains the previously seen patterns will require a large amount of memory as it ngrows. What other approach can we use to overcome this problem.

+4
source share
2 answers

1- , , .

, C - ( C = [1, 5]). A[i][j] - i 0 j.

, j, A[0][j] = 1, 0: .

, A[8][1], 8 . , . , , A[8][0] . , 3 cents left, A[3][1] .

A[8][0] , A[8][0] = A[7][0] = ... = A[0][0] = 1.

A[3][1] 3 < 5, A[3][1] = A[3][0]. A[3][0] = A[2][0] = ... = 1, .

:

A[i][j] = A[i][j-1] if i < C[j]
          else A[i][j-1] + A[i-C[j]][j]

.

+2

1 , , , .

, floor(N/5) + 1

[0..N/5] 5 , 1

, /.

, , .

C(x, m):= The # of ways to make number x using first m type of coins

, :

C(x, m) = C(x-coin_type[m], m) + C(x, m-1) , m-

, , .

, -

For i = 0 to # of coin_type
    For j = 0 to n
       C(j, i) = C(j-coin_type[i], i) + C(j, i-1)

, . coin_type = {1,3,5}, {1}, {1,3}, , {1,3, 5}.

, {3,1,5}, {1,5,3}... .. , , -

+2

More articles:


All Articles