algorithm - 动态规划 - 棒材切割

Question

前几天我在看 CLRS 只是为了稍微提神一下，结果遇到了经典的杆切割问题。

经典的自下而上解决方案如下:

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = -1
5:    for i = 1 to j
6:       q = max(q, p[i] + r[j-i])
7:    r[j] = q
8: return r[n]

现在我一直在想一件事。为什么我们继续在 L.6 上重复使用 p[i]？我的意思是假设我们有 j = 4 然后它会计算以下组合:

1 + 3
2 + 2
3 + 1
4 + 0

计算“3 + 1”两次真的有什么意义呢？我的建议是不要使用 p[] 而只使用 r[] 并在 floor(j/2) 处停止。

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = p[j]
5:    for i = 1 to floor(j/2)
6:       q = max(q, r[i] + r[j-i])
7:    r[j] = q
8: return r[n]

有没有人发现这种方法有问题？

谢谢，

Answer 1

您的优化没有任何问题。我之前在杆切割问题中看到它被多次使用/提及(这里只是一个例子:http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec09.349.pdf)。没有完美的教科书。这可能是 CLRS 的错误，或者他们只是觉得提及此类优化会使本书变得困惑。

通常，此类介绍性书籍将侧重于高级概念，而将寻找此类微不足道的优化留给读者。考虑冒泡排序:并不是每个人都会提到一个简单的优化事实，即内部循环 j 只需要上升到 i。