遞歸混淆 - 杆切割算法

Question

我試圖實現CLRS中說明的杆切割算法，但是我發現自己很難獲得正確的索引。這裏是我的memoization版本的實現：

import sys 
def rod_cutting_memoization(p,n): 
    r = [None for i in range(n+1)] 
    r[0] = 0 
    rod_cutting_memoization_aux(p,n,r) 
    return r 

def rod_cutting_memoization_aux(p,n,r): 
    print r 
    if r[n] is not None: 
     return r[n] 
    if n is 0: 
     return 0 
    else: 
     q = -100 
     for i in range(n): 
      q = max(q, p[i] + rod_cutting_memoization_aux(p,n-i-1,r)) 
    r[n] = q 

p=[1, 5, 8, 9, 10, 17, 17, 20, 24, 30] 
n = int(sys.argv[1]) 
print rod_cutting_memoization(p,n) 

從n = 2開始，代碼是說int + None。本書中的僞代碼是用從1開始的索引編寫的。我總是在將索引從1改爲0的轉換算法中遇到這個問題。有沒有解決此問題的一般方法？

Answer 1

您的遞歸rod_cutting_memoization_aux()函數僅返回r[n] is not None和n == 0的值。如果這兩個條件都不是True，則該功能只是在沒有明確的return的情況下結束，這意味着返回None。

這意味着該行：

q = max(q, p[i] + rod_cutting_memoization_aux(p,n-i-1,r)) 

會嘗試與None總結p[i]爲p, n - i - 1, r一些值。

您需要從None以外的東西返回以防止這種情況;大概是一個整數需要返回。