前几天，我在看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]
有人认为这种方法有问题吗？
谢谢，
最佳答案
您的优化没有任何问题。我已经看过它在杆切割问题中使用过几次/提到过(这里只是一个示例:http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec09.349.pdf)。没有完美的教科书之类的东西。这可能是CLRS方面的一个错误，或者他们只是觉得提及此类优化会令书本困惑。
通常，此类入门书籍将侧重于高级概念，而将这些琐碎的优化工作留给读者。考虑一下冒泡排序:并不是每个人都会提到一个事实，即内部循环j仅需达到i的简单优化这一事实。
关于algorithm - 动态编程-杆切割，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7198585/