python - 递归混淆——切杆算法

Question

我正在尝试实现 CLRS 中说明的杆切割算法，但我发现自己很难获得正确的索引。这是我对内存版本的实现:

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))

将尝试求和 p[i]与 None对于 p, n - i - 1, r 的某些值.

您需要返回 除 None 之外的其他内容 从递归调用中防止这种情况；大概需要返回一个整数。