Я изучаю динамическое c программирование. Недавно я нашел этот код для вычисления количества подмножеств, сумма которых равна заданному числу. Но я не могу понять, как обновляется значение mem.
def count_sets(arr,total):
mem = {}
return dp(arr,total,len(arr)-1, mem)
def dp(arr,total, i, mem):
key = str(total)+':'+str(i)
if key in mem:
return mem[key]
if total == 0:
return 1
elif total < 0 or i < 0:
return 0
elif total < arr[i]:
to_return = dp(arr,total, i-1, mem)
else:
to_return = (dp(arr,total - arr[i], i-1, mem) \
+ dp(arr,total, i-1, mem))
mem[key] = to_return
return to_return
if __name__ == "__main__":
c = count_sets([2,4,6,10],16)
print(c) # print 2
Хотя первый вызов dp (arr, total, i, mem) в algorthm имеет {} для mem.
Так что, если я только возвращаю сумму пока подмножества (также известные как to_return), почему mem обновляется, если не возвращает, не должно ли его значение жить только в рамках функции?
Может ли кто-нибудь помочь мне лучше понять сферу действия переменная mem? и почему он обновляется? спасибо!
Другой пример, который я пытался понять, был:
def add(x):
x = x+1
def main():
a = 2
add(a)
print(a)#prints 2
main()