Coin change problem: top down approach seems to not be polynomial

Question

The coin change problem (see leet code page here) gives us some coins of certain denominations in an array, c. Then, given a target amount, t, we want to find the minimum coins required to get that target amount. This is in principal, very similar to the optimum rod cutting problem described in section 15.1 of the book "Introduction to algorithms" by Cormen et.al.

In line with their approach, I implemented top-down and bottom-up versions of the coin change problem. the bottom-up approach works quite well and solves all test cases fairly quickly. The top-down version however, takes a very long time on certain inputs, suggesting it isn't polynomial in the inputs. It does produce the right answer for the test cases it manages to solve. Does anyone have a clue into why it might not be polynomial? Or substantially slower than the bottom up version?

def memoised_coin_chg(c,u):
  r=np.ones(u+1)*np.inf
  r[0]=0
  return memoised_coin_chg_aux(c,u,r)

def memoised_coin_chg_aux(c,u,r):
  if r[u]<np.inf:
      return r[u]
  if u==0:
      q=0
  else:
      q=np.inf
      for i in range(len(c)):
          if u >= c[i]:
              q=min(q,memoised_coin_chg_aux(c,u-c[i],r))
  r[u]=q+1
  return q+1

def tst3():
  res=memoised_coin_chg([1,2,5],11)
  print(res)
  res=memoised_coin_chg([2],3)
  print(res)
  res=memoised_coin_chg([1,2147483647],2)
  print(res)
  ## Too slow to produce results from here on..
  res=memoised_coin_chg([27,40,244,168,383],6989)
  print(res)
  res = memoised_coin_chg([186,419,83,408],6249)
  print(res)
  res = memoised_coin_chg([282,116,57,239,103,89,167],4856)
  print(res)

Answer 1

If an amount is not reachable with given coin types, you leave its value as inf in the memorized values array. But inf also means that value has not been visited before. That is, every time we see an inf, we calculate that value from scratch, and sometimes write inf back again.

So, if you want to make this polynomial, you need to differentiate between an inf that means "not visited", and an inf that means "visited but not reachable". My suggestion would be using a -1 for "not visited" values:

import numpy as np;

def memoised_coin_chg(c,u):
  r=np.ones(u+1)* -1 # change 1
  r[0]=0
  return memoised_coin_chg_aux(c,u,r)

def memoised_coin_chg_aux(c,u,r):
  if r[u] != -1: # change 2
      return r[u]
  # removed u = 0 check because r[0] is already initialized to 0
  q=np.inf
  for i in range(len(c)):
      if u >= c[i]:
          q=min(q,memoised_coin_chg_aux(c,u-c[i],r))
  r[u]=q+1
  return q+1

def tst3():
  res=memoised_coin_chg([1,2,5],11)
  print(res)
  res=memoised_coin_chg([2],3)
  print(res)
  res=memoised_coin_chg([1,2147483647],2)
  print(res)
  ## Too slow to produce results from here on..
  res=memoised_coin_chg([27,40,244,168,383],6989)
  print(res)
  res = memoised_coin_chg([186,419,83,408],6249)
  print(res)
  res = memoised_coin_chg([282,116,57,239,103,89,167],4856)
  print(res)

tst3()