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

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

虽然您的实施是典型的 Coin Change Problem 的扭曲，少了 1 个维度，这可能会导致您重复计算很多组合，但我认为对于给定的硬币系统来说并没有那么复杂。

我认为解决方案很简单 floor(N/5) + 1

因为你只能用[0..N/5]的5分，剩下的你必须用1分

这可以很容易地完成，因为您的硬币系统是规范的，并且可以应用贪心算法/心态。

如果你非要用动态规划来解题的话，需要加一个维度，代表用的是哪种币种。此方法适用于任何硬币系统

定义C(x, m):= The # of ways to make number x using first m type of coins

所以现在递归公式变成：

C(x, m) = C(x-coin_type[m], m) + C(x, m-1)，表示您选择使用第m种硬币，或者不使用

这是要点，为什么这个循环有效而你的无效，是状态的迭代顺序。

使用这个递归公式，我们可以做类似的事情

For i = 0 to # of coin_type
    For j = 0 to n
       C(j, i) = C(j-coin_type[i], i) + C(j, i-1)

注意外循环强制对硬币类型的迭代进行排序。比如coin_type = {1,3,5}，循环会先统计只使用{1}的方式，然后循环的下一次循环会统计使用{1,3}的方式，最后一次循环会统计使用{1, 3,5}。

您永远不会使用 {3,1,5} 或 {1,5,3}...等计算方式。硬币类型的顺序是固定的，这意味着你不会重复计算任何东西

Answer 2

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

假设 C 是您按升序排列的硬币价值列表（在您的示例中，C = [1, 5]）。然后让 A[i][j] 是用硬币 0 到 j.

表示价值 i 的方式的数量

我们知道对于任何 j，A[0][j] = 1 因为只有一种方式来表示值 0：没有硬币。

现在假设我们要找到 A[8][1]，用便士和五分硬币表示 8 美分的方法的数量。每个代表要么使用镍，要么不使用。如果我们不使用镍，那么我们只能使用便士，所以有 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]

此算法适用于任何一组硬币价值。

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

Solving Dynamic Programming Problem on coins

python

recursion

dynamic-programming

memoization