title: Memoizing Coin Change
body: <p>I want to convert my coin change function to memoized function<br>
  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.<br>
  what I did is:
  <br></p>
  
  <pre><code>def change(a,kinds=(50,20,10,5,1)):
      if(a==0):
              return 1
      if(a&lt;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)&gt;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))
  </code></pre>
  
  <p>I would like to get some suggestions , or maybe there is another way to do that.<br>
  thanks.</p>
  
  <p><br></p>
  
  <p><strong>EDIT</strong><br>
  Memoized version:<br></p>
  
  <pre><code>def change(a,kinds=(50,20,10,5,1)):
      if(a==0):
              return 1
      if(a&lt;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))
  </code></pre>