我的动态规划程序令人惊讶地添加数字而不是解决方案

Question

在“Introduction to Algorithms”一书中，我试图实现一个称为“rod-cutting-program”的动态规划问题。这里我有一个数组定义可变长度的杆的价格。因此，数组 {1, 4} 定义了长度为 1 英寸的杆的价格为 1$，长度为 4 的杆的价格也为 4$。我得到一个输入，它是给定杆的长度。我的目标是将杆切成多段，使每段的长度保持整数，使每段的总价最大化。

这是我的程序

print("Input Length Prices: ")
p = [int(x) for x in input().split()]

def cut_rod(n):
    if n == 0:
        return 0
    q = -1
    for i in range(1, n+1):
        q = max(q, p[i-1] + cut_rod(n-1))

    return q

print("Input Length to Cut: ")
print(cut_rod(int(input())))

这是我的输入和输出。

输入

1 4
2

输出

5 (This is the sum of 1 and 4)

预期输出

因此，它给出的不是最大总价，而是所有长度价格的总和。我也尝试了其他几种输入。在所有情况下，它都给出总和。很奇怪。

编辑：杆也可以保持原状。

Answer 1

你的程序有两个问题：

#1) 在你的递归调用中你需要 cut_rod(n-i) 而不是 cut_rod(n-1)。删除一段长度 i 后，您还剩下 p-i。

#2) 您重复调用 cut_rod 递归，并且对于 n 的大值，您正在进行 O(n*n) 递归调用。动态规划的要点是计算较小结果的值，然后缓存它们而不是每次需要它们时都重新计算它们。

幸运的是，Python 让这一切变得简单。只需使用 @functools.lru_cache(None)

注释您的代码

===更正===

我在上面写到这段没有缓存的代码是O(n*n)。这实际上是指数级的或更糟。斐波那契数的朴素递归实现是指数的，并且只对每个大于 2 的参数 n 进行两次递归调用；该程序使 n - 1.

我的动态规划程序令人惊讶地添加数字而不是解决方案

My Dynamic Programming program is surprisingly adding numbers instead of solution

python

algorithm

recursion

dynamic-programming