问题描述:

Consider the problem in which you have a value of `N`

and you need to calculate how many ways you can sum up to `N`

dollars using `[1,2,5,10,20,50,100]`

Dollar bills.

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 take into effect the order of the summed parts. For example, `comb(4)`

will yield 5 results: `[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]`

whereas there are actually 3 results (`[2,1,1],[1,2,1],[1,1,2]`

are all the same).

What is the DP idiom for calculating this problem? (*non-elegant* solutions such as generating all possible solutions and removing duplicates are not welcome)

You should not go from begining each time, but at max from were you came from at each depth. That mean that you have to pass two parameters, start and remaining total.

```
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
```

or equivalent (it might be more readable)

```
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
```

Not sure about any DP idioms, but you could try using Generating Functions.

What we need to find is the coefficient of x^N in

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

(number of times 1 appears*1 + number of times 5 appears * 5 + ... )

Which is same as the reciprocal of

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

You can now factorize each in terms of products of roots of unity, split the reciprocal in terms of Partial Fractions (which is a one time step) and find the coefficient of x^N in each (which will be of the form Polynomial/(x-w)) and add them up.

You could do some DP in calculating the roots of unity.

Terminology: What you are looking for is the "integer partitions" into prescibed parts (you should replace "combinations" in the title). Ignoring the "dynamic programming" part of the question, a routine for your problem is given in the first section of chapter 16 ("Integer partitions", p.339ff) of the fxtbook, online at http://www.jjj.de/fxt/#fxtbook

您可能感兴趣的文章：

- kernel - Operating system question
- Is it possible to open incomplete video-file for playback using directshow?
- objective c - Smaller UIView in UIScrollView to stop touches
- php - How to modify .htaccess
- c - LuaSocket, Lua 5.2 and Redis
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**