python中的memoization，關閉一個錯誤

我目前正在採取算法類。我正在用python測試它們中的很多，包括動態編程。這是一個實施自下而上的杆切割實施。python中的memoization，關閉一個錯誤

由於錯誤的錯誤，它不起作用。是否有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

來源

2012-10-26 The Internet

最高價格有一對夫婦的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開始。你想調整你的算法來處理語言。

來源

2012-10-26 18:20:30

對於'enumerate（）'+1。在Python 2.6和更高版本中，'enumerate（）'爲起始索引提供了一個額外的參數，這在處理基於1的對象時可能會有所幫助。 – kindall

在你的情況下，off-by-one是r[n]的結果，其中len(r)==n。你要麼寫r[n-1]，或，更優選，r[-1]，意思是「的r的最後一個元素」，以相同的方式將r[-2]意味着「倒數第二」等的

無關的，但有用的：[ 0 for i in range(n) ]可以寫成[0] * n

來源

2012-10-26 18:20:35 bereal

[0] * n ==美麗 –

雖然使用[x] * n語法時要小心。 – inspectorG4dget

當處理可變類型時爲真。實際上'[[]] * 3'會創建一個引用列表，所以'lst [0] .append（1）'會給你'[[1]，[1]，[1]] '。 – bereal

在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-26 19:11:19

不錯的解決方案。但我不知道基於插入的版本是否比您的原始版本更可取。使用'reversed'遍歷一個列表是O（1），但是在列表的開頭插入O（n）。從長遠來看，這並不重要，因爲整個算法是O（n ** 2），但我猜測使用插入會減慢一個常數倍數。 – senderle

@senderle你有一點。回滾。 –

你也可以考慮使用'deque'而不是'list'。然後插入前面將是O（1）。 –

python中的memoization，關閉一個錯誤

回答

相關問題