硬币兑换问题:自上而下的方法似乎不是多项式

Question

硬币兑换问题(请参阅此处的leet代码页(在数组c中给了我们一些特定面额的硬币。然后，给定目标金额t，我们想找到获得该目标金额所需的最小硬币。这在原理上非常类似于书"；算法介绍"；Cormen等人

根据他们的方法，我实现了自上而下和自下而上的硬币兑换问题。自底向上的方法工作得很好，可以很快地解决所有测试用例。然而，自上而下的版本在某些输入上花费了很长时间，这表明它在输入中不是多项式。它确实为它设法解决的测试用例提供了正确的答案。有人知道为什么它可能不是多项式吗？或者比自下而上的版本慢得多？

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，它意味着"；未访问"；，以及CCD_ 6；"已访问但无法访问"；。我的建议是用-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()