python中的memoization，只有一个错误

Question

我现在正在上一门算法课。我正在用python测试其中的很多东西，包括动态编程。下面是一个实现自下而上切割棒的实现。

因为off-by-one错误，所以它不能工作。在python中是否有一个全局设置，可以将默认数组索引更改为1而不是0？或者有人能为我提供一个更好的策略来克服我遇到的一百万次的错误。这太烦人了。

def bottom_up_memo_cut_rod(p,n):
    r = [ 0 for i in range(n) ]
    r[0] = 0
    for j in range(n):
        q = -1
        for i in range(j):
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

bottom_up_memo_cut_rod([1,5,8,9], 4)

答案应该是10，在这种情况下，将4除以(2,2)得到的最大价格为10。

Answer 1

Python中有一些东西可能会对您有所帮助。内置的enumerate是一个很好的工具。

for idx, val_at_idx in enumerate(aList):
  # idx is the 0-indexed position, val_at_idx is the actual value.

如果绝对必要，您还可以使用列表切片和枚举来移位索引：

for idxOffBy1, val_at_wrong_idx in enumerate(aList[1:]):
  # idx here will be 0, but the value will be be from position 1 in the original list.

但实际上，你不会想要改变解释器，让列表从索引1开始。你想要调整你的算法，使之与语言一起工作。

Answer 2

在Python中，您通常可以完全避免使用索引。该算法可以写成这样：

def bottom_up_memo_cut_rod(p,n):
    r = [0]
    for dummy in p:
        r.append(max(a + b for a, b in zip(reversed(r),p)))
    return r[-1]

print bottom_up_memo_cut_rod([1,5,8,9], 4)
#10

Answer 3

在您的例子中，off-by-one是r[n] where len(r)==n的结果。你要么写r[n-1]，要么更好地写r[-1]，意思是“r的最后一个元素”，就像r[-2]表示“倒数第二”一样。

无关，但很有用:可以将[ 0 for i in range(n) ]编写为[0] * n