组合的动态编程习语

Question

考虑一下你有一个价值的问题N,你需要计算N使用[1,2,5,10,20,50,100]Dollar账单总计美元的方法.

考虑经典的DP解决方案:

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 

它不会影响求和部分的顺序.例如,comb(4)将产生5个结果:[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]而实际上有3个结果([2,1,1],[1,2,1],[1,1,2]都是相同的).

用于计算此问题的DP习惯用法是什么？(不受欢迎的非优雅解决方案,例如生成所有可能的解决方案并删除重复项)

Answer 1

不确定任何DP习语,但您可以尝试使用生成函数.

我们需要找到的是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-X)(1-x ^ 5)(1-x ^ 10)(1-x ^ 20)(1-x ^ 50)(1-x ^ 100).

你现在可以根据统一根的乘积来对每个因子进行因式分解,用部分分数(这是一个步骤)分割倒数,并找出每个中的x ^ N的系数(其形式为多项式/( xw))并将它们加起来.

你可以在计算统一的根源时做一些DP.

Answer 2

你不应该每次都从开始,但最大的时候你是从每个深度来的.这意味着您必须传递两个参数,即开始和剩余总数.

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