如何记忆函数

Question

问题是有一个数字金字塔，你试图通过“滑动”金字塔来找到最大的总和

我做了一个基本的“记忆”技术，制作了一个数组，并在每个函数调用中传递它。显然，这并不理想，因为数组的大小是固定的，我不能让数组依赖于初始金字塔大小，因为可选参数必须独立于此。我不知道如何使数组大小取决于金字塔的大小，而不硬编码它，或者在调用函数时显式要求初始数组和初始大小

def LSD2(pyramid, m = 0, n = 0, L = []):
    if len(L) == 0:
      L = [[None]*1000 for i in range(1000)]
    if len(pyramid) == 0:
      return 0

    else:
      if L[n][m] != None:
        return L[n][m]
      elif L[n-1][m] != None and L[n-1][m-1] != None:
        return max(pyramid[n][m] + max(L[n-1][m], L[n-1][m-1]))
      L[n][m] = pyramid[0][m] + max(LSD2(pyramid[1:], m, n + 1, L), LSD2(pyramid[1:], m+1, n + 1, L))
    return L[n][m]

Answer 1

以美元计。指出，Python只有称为lists的动态数组。可以分别使用.append和.remove添加和删除元素。也就是说，考虑到您的用例，使用元组键的dict可能是更好的选择。所以你的代码会变成：

def LSD2(pyramid, m = 0, n = 0, L = {}):
    if len(pyramid) == 0:
      return 0

    if (n, m) in L:
      return L[(n, m)]
    elif L.get((n-1, m), None) and L.get((n-1, m-1), None):
      return max(pyramid[n][m] + max(L[(n-1, m)], L[(n-1, m-1)]

    L[(n, m)] = pyramid[0][m] + max(LSD2(pyramid[1:], m, n + 1, L), LSD2(pyramid[1:], m+1, n + 1, L))  
    return L[(n, m)]