使用记忆法在动态规划中解决这个问题

Question

我正在使用Python研究动态编程概念。我设计了一个简单的代码，对于每个递归，它将给定的输入(n)除以2，并添加到memo字典中。我想要备忘录字典作为此函数的返回值。

n = 16
def myfunc(n, memo={}):
if n in memo : return memo[n]
if n == 0 : return 0
if n == 1 : return 1
if n % 2 == 0:
memo[n] = myfunc(n // 2)
else:
pass
return memo   
res = myfunc(n)
print(res) 

但是当我执行上面的代码时，我得到的结果是:

{2: 1, 4: {...}, 8: {...}, 16: {...}}

我不明白这个{...}是从哪里来的?

我想要结果{2: 1, 4: 1, 8: 1, 16: 1}，逻辑上。

Answer 1

问题是，您一直返回相同的memo对象。试试这样做:

def myfunc(n, memo={}):
if n <= 1: return
if n % 2 == 0:
memo[n] = 1
myfunc(n // 2, memo)
return memo

res = myfunc(16)
print(res)