组合的动态编程习惯用法

你不应该每次都从一开始就走,但在最大限度上,你是从每个深度来的。 这意味着你必须通过两个参数,开始和剩余总数。

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 

不确定任何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-x)(1-x^5)(1-x^10)(1-x^20)(1-x^50)(1-x^100)。

你现在可以用统一根的积来分解每一个,用 Partial Fractions (这是一个一次性步骤),在每个步骤中找出x^n的系数(其形式为多项式/(x-w)),并将其相加。

你可以做一些dp来计算统一的根。

术语:您要查找的是“整数分区” 到预先设定的部分(您应该替换标题中的“组合”)。 忽略问题的“动态编程”部分,一个例程 因为你的问题在第16章的第一节 fxtbook的(“整数分区”,第339ff页),在线: http://www.jjj.de/fxt/#fxtbook