考虑以下问题
给出无限数量的镍(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.
更多推荐
解决硬币上的动态编程问题
发布评论