硬币找零问题：自上而下的方法似乎不是多项式的

Question

硬币找零问题（参见 leet 代码页 here）为我们提供了数组中某些面额的硬币，c。然后，给定一个目标数量 t，我们想要找到获得该目标数量所需的最少硬币。这在原则上与 Cormen et.al.

一书“算法导论”第 15.1 节中描述的最佳杆切割问题非常相似

根据他们的方法，我实现了硬币找零问题的自上而下和自下而上版本。自下而上的方法效果很好，可以很快地解决所有测试用例。然而，自上而下的版本在某些输入上需要很长时间，这表明它在输入中不是多项式的。它确实为它设法解决的测试用例产生了正确的答案。有谁知道为什么它可能不是多项式？或者比自下而上的版本慢得多？

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

如果给定的硬币类型无法达到某个数量，则将其值保留为 inf 在记忆值数组中。但是 inf 也意味着之前没有访问过该值。也就是说，每次我们看到 inf 时，我们都会从头开始计算该值，有时会再次写回 inf。

因此，如果要生成此多项式，则需要区分表示“未访问过”的 inf 和表示“已访问但无法访问”的 inf。我的建议是对“未访问”值使用 -1：

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

硬币找零问题：自上而下的方法似乎不是多项式的

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

python

dynamic-programming

coin-change