python - 内存零钱

Question

我想将我的硬币找零功能转换为内存功能
为此，我决定使用字典，这样字典中的键就是硬币，而值将是一个列表，其中包含可以更改“键”硬币的所有硬币。
我所做的是:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0

    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):

        if len(cache)>0 and kinds in cache[a]:
            return 1
        else:
            if(f(a,kinds)==1):
                cache[a]=kinds // or maybe cache[a].append(..)
                return cache[a]+memo(a-kinds[0],kinds)+memo(a,kinds[1:])
    return memo

memC=memoizeChange(change)
kinds=(50,20,10,5,1)
print(memC(10,kinds))

我想得到一些建议，或者也许有另一种方法可以做到这一点。
谢谢。

编辑
内存版本:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0
    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):
        if not (a,kinds) in cache:
                cache[(a,kinds)]=f(a,kinds)
        return cache[(a,kinds)]
    return memo

change=memoizeChange(change)
print(change(10))

Answer 1

它没有按要求回答你的问题，但是如果 r[0] 到 r[i] 是用你的前 k 个面额进行更改的方法的数量，那么 r[i+1] 就是数量用前 k-1 个面额加上 r[i-k] 进行找零的方法。这为您正在解决的问题提供了一个优雅的解决方案:

def change(total, denominations):
    r = [1] + [0] * total
    for k in denominations:
        for i in xrange(k, len(r)):
            r[i] += r[i - k]
    return r[total]

print change(100, (50, 20, 10, 5, 1))

Polya 的“How to solve it”一书中讨论了这种方法。一般来说，使用内存来改进递归解决方案是一种在 Python 中编写动态编程解决方案的简单方法，但我个人认为，能够降低一个级别并弄清楚如何准确地构建中间结果是一项重要技能动态规划解决方案中的表。通常(并在此处举例说明)，结果更快且更易于阅读(尽管首先更难编码)。