2

我目前正在学习算法课程。我在 python 中测试了很多，包括动态编程。这是自下而上的杆切割实现的实现。

由于一个错误，它不起作用。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 的最高价格。

4

3 回答 3

3

Python中有几件事可以帮助你。内置enumerate是一个伟大的。

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

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

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 开始。您想调整算法以使用该语言。

于 2012-10-26T18:20:30.583 回答
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
于 2012-10-26T19:11:19.527 回答
-1

在您的情况下，一对一是r[n]where的结果len(r)==n。你要么写r[n-1]，或者，更优选地，，r[-1]这意味着“的最后一个元素r”，同样的方式r[-2]将意味着“倒数第二个”等等。

无关，但有用：[ 0 for i in range(n) ]可以写成[0] * n

于 2012-10-26T18:20:35.120 回答