Dynamic Programming Idiom for Combinations

Question

Consider a problem in which you have a value N, and you need to calculate how many ways you can sum up to Ndollars using [1,2,5,10,20,50,100]Dollar accounts .

Consider the classic DP solution:

C = [1,2,5,10,20,50,100]

def comb(p):
    if p==0:
        return 1
    c = 0
    for x in C:
        if x <= p:
            c += comb(p-x)
    return c 

It does not introduce the order of the summed parts. For example, it comb(4)will give 5 results: [1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]whereas in fact there are 3 results ( [2,1,1],[1,2,1],[1,1,2]all are the same).

What is the DP ID to calculate this problem? (non-elegant solutions, such as creating all possible solutions and removing duplicates, are not welcome)

Answer 1

, . , . , , .

C = [1,5,10,20,50,100]

def comb(p,start=0):
    if p==0:
        return 1
    c = 0
    for i,x in enumerate(C[start:]):
        if x <= p:
            c += comb(p-x,i+start)
    return c 

( )

C = [1,5,10,20,50,100]

def comb(p,start=0):
    if p==0:
        return 1
    c = 0
    for i in range(start,len(C)):
        x=C[i]
        if x <= p:
            c += comb(p-x,i)
    return c 

Answer 2

- DP, Generating Functions.

x ^ N

(1 + x + x ^ 2 +...) (1 + x ^ 5 + x ^ 10 +...) (1 + x ^ 10 + x ^ 20 +...)... ( 1 + x ^ 100 + x ^ 200 +...)

( 1 * 1 + 5 * 5 +...)

,

(1-) (1- ^ 5) (1- ^ 10) (1- ^ 20) (1- ^ 50) (1- ^ 100).

, ( ) x ^ N ( Polynomial/(xw)) .

- DP .

Answer 3

: , , " ", ( "" ). " " , 16 ( " ", .339ff) fxtbook, http://www.jjj.de/fxt/#fxtbook