python - 解决硬币上的动态规划问题

Question

考虑下面的问题

Given an infinite number of nickels (5 cents) and pennies (1 cent). Write a code to calculate a number of ways of representing n cents.

我的代码

def coins(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    else:
        if (cnt_lst[n-1] == 0):
            cnt_lst[n-1] = coins(n-1) + coins(n-5)
        return cnt_lst[n-1]

if __name__ == "__main__":
    cnt = int(input())
    cnt_lst = [0] * cnt #Memiozation
    ret = coins(cnt)
    print(ret)

上述方法计算重复模式不止一个(显然我没有明确检查它们)。

[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc

随着 n 的增长，维护另一个包含先前看到的模式的列表将需要大量内存。我们可以使用什么其他方法来克服这个问题？

Answer 1

您可以使用二维数组代替一维列表，其中一维是总数，第二维是可用的最大面值硬币。

假设C是您按升序排列的硬币值列表(在您的示例中为 C = [1, 5] )。然后让A[i][j]是表示值的方式的数量 i用硬币 0通过j .

我们知道对于任何 j , A[0][j] = 1因为只有一种方法可以表示值 0 : 没有硬币。

现在假设我们要查找A[8][1] , 用便士和镍币表示 8 cents 的方法数。每个代表要么使用镍，要么不使用。如果我们不使用镍，那么我们只能使用便士，所以有 A[8][0]方法来做到这一点。如果我们确实使用镍，那么我们有 3还剩美分所以有A[3][1]方法。

计算A[8][0]我们只有一枚硬币，所以 A[8][0] = A[7][0] = ... = A[0][0] = 1 .

计算A[3][1]自 3 < 5 以来我们不能使用镍, 所以 A[3][1] = A[3][0] .从那里我们有A[3][0] = A[2][0] = ... = 1如上。

一般来说:

A[i][j] = A[i][j-1] if i < C[j]
          else A[i][j-1] + A[i-C[j]][j]

此算法适用于任何一组硬币值(value)。