动态规划 - 杆切割

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 []并停在楼层(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。