下面的代码:
import sys
MOD = 10 ** 9
sys.setrecursionlimit(3000000)
primes = [2,3,5,7,11,13]
F = [1, 2]
cols = 1 + 2
rows = F[-1] + 2
memo = [[-1] * (cols)] * rows
def b(n, i):
try:
print("Called b(", n, i, "), whose memorised value currently =", memo[n][i])
if n < 0:
return 0
assert(memo[2][0]<0)
if memo[n][i] >= 0:
print(n, i, "is alredy set")
return memo[n][i]
elif n == 0:
print("setting memo(", n, i, ") to 1")
memo[n][i] = 1
elif i == 0:
print("setting memo(", n, i, ") to 0")
memo[n][i] = 0
else:
memo[n][i] = (b(n, i - 1) + b(n - primes[i-1], i) * primes[i-1]) % MOD
print("setting recursively memo(", n, i, ") to ", memo[n][i])
print("Returning from b(", n, i, "), whose memorised value after update =", memo[n][i])
return memo[n][i]
except Exception as e:
print(e)
raise e
print("memo=",memo)
n = 1
an = b(n, 0)
print("memo[2][0]=",memo[2][0])
作为调试工作,我在最后一行打印memo[2][0]
。memo[2][0]
应该是-1,因为它没有被递归更新,只是最初设置为-1。
memo= [[-1, -1, -1], [-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
Called b( 1 0 ), whose memorised value currently = -1
setting memo( 1 0 ) to 0
Returning from b( 1 0 ), whose memorised value after update = 0
memo[2][0]= 0
预期输出应为:
memo= [[-1, -1, -1], [-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
Called b( 1 0 ), whose memorised value currently = -1
setting memo( 1 0 ) to 0
Returning from b( 1 0 ), whose memorised value after update = 0
memo[2][0]= -1
1条答案
按热度按时间hvvq6cgz1#
我认为this是根本原因
为解决此问题,已将
memo = [[-1] * (cols)] * rows
更改为memo = [[-1]*cols for _ in range(rows)]