纪念硬币找零 [英] Memoizing Coin Change

问题描述

我想将找零功能转换为记忆功能
为此，我决定使用字典，以便字典中的键将是硬币，而值将是包含所有可以更改键"硬币的硬币的列表.
我所做的是:

I want to convert my coin change function to memoized function
to do that, I decided to use dictionary so that a key in my dict will be the coin and the value will be a list that contain all the coins that can change the "key" coin.
what I did is:

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))

我想获得一些建议，或者还有另一种方法.
谢谢.

I would like to get some suggestions , or maybe there is another way to do that.
thanks.

编辑
备注版本:

EDIT
Memoized version:

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))

推荐答案

当您可以使用通用的预先编写的装饰器时，不必编写专门的记忆装饰器，例如直接来自 PythonDecoratorLibrary :

It's not necessary to write a specialized memorizing decorator when you could just use a generic pre-written one...such as the following straight from the PythonDecoratorLibrary:

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

然后您可以将其应用到您的change()函数(或其他任何函数，因为它是通用的)，如下所示:

You could then apply it to yourchange()function (or any other, since it's generic) like this:

@memoized
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:])

print(change(10))  # 4

这篇关于纪念硬币找零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！