带memoize的Dp

Question

这是“算法简介”dp章节中的一个问题。

为了获得最大的利益，我们必须砍掉一块很长的钢

​

​

第一行是length，第二行是price。

def cut_rod_mem(n, p):
m = [0]
for i in range(10):
    m.append(-1)

def inner(n, p):
    if m[n]!=-1:
        return m[n]
    for i in range(1, n + 1):
        t = p[i] + inner(n - i, p)
        if t > m[n]:
            m[n] = t
    return m[n]

return inner(n,p)

我不明白这个列表会不会超出范围？

Answer 1

它不会超出范围，因为数组的元素是从0 to n-1索引的，也就是上面的0 to 9。在函数中，内部的for循环来自1 to n，因此内部的(n - i, p)在值为inner(9, p)的范围内.....inner(0, p)。