解决硬币上的动态编程问题 [英] Solving Dynamic Programming Problem on coins

问题描述

考虑以下问题

给出无限数量的镍(5美分)和几美分(1美分).编写代码以计算代表n美分的多种方式.

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)

上述方法对重复模式的计数不止一个(显然，我没有明确检查它们).

Above approach counting repeated patterns more than one (obviously I'm not checking them explicitly).

[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1]等

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

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

Maintaining another list which holds the previously seen patterns will require a lot of memory as n grows. What another approach we can use to overcome this problem?

推荐答案

您可以使用二维数组，而不是使用一维列表，其中一维是总数，第二维是最大值可用硬币.

Instead of using a 1-dimensional list, you can use a 2-dimensional array where one dimension is the total, and the second dimension is the largest-value coin available.

比方说，C是您的硬币值列表，以升序排列(在您的示例中，为C = [1, 5]).然后让A[i][j]是用硬币0至j表示值i的方式的数量.

Let's say C is your list of coin values in ascending order (in your example, C = [1, 5]). Then let A[i][j] be the number of ways to represent value i with coins 0 through j.

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

We know that for any j, A[0][j] = 1 because there is exactly one way to represent the value 0: no coins.

现在假设我们要查找A[8][1]，即用几美分和镍币代表8美分的方式数量.每个表述要么使用镍，要么不使用.如果我们不使用镍，那么我们只能使用几美分，因此有A[8][0]方式可以做到这一点.如果我们使用镍，则还剩3美分，所以有A[3][1]个方法可以做到这一点.

Now suppose we want to find A[8][1], the number of ways to represents 8 cents with pennies and nickels. Each representation will either use a nickel or it won't. If we don't use a nickel then we can only use pennies, so there are A[8][0] ways to do this. If we do use a nickel then we have 3 cents left so there are A[3][1] ways to do this.

要计算A[8][0]，我们只有一个硬币可用，因此A[8][0] = A[7][0] = ... = A[0][0] = 1.

To compute A[8][0] we only have one coin available so 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.

To compute A[3][1] we can't use a nickel since 3 < 5, so A[3][1] = A[3][0]. From there we have A[3][0] = A[2][0] = ... = 1 as above.

通常:

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

该算法适用于任何一组硬币值.

This algorithm works for any set of coin values.

这篇关于解决硬币上的动态编程问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！