algorithm - 组合的动态规划习语

考虑您拥有 N 值的问题，并且您需要计算使用 N 美元钞票可以将 [1,2,5,10,20,50,100] 美元加起来的方式有多少。

考虑经典的 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 习语是什么？ (不欢迎非优雅的解决方案，例如生成所有可能的解决方案并删除重复项)

最佳答案

您不应该每次都从头开始，但最多从每个深度开始。
这意味着您必须传递两个参数，开始和剩余总数。

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

关于algorithm - 组合的动态规划习语，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3444144/