递归混淆 - 杆切割算法

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以外的东西返回以防止这种情况;大概是一个整数需要返回。