算法导论-动态规划-钢条切割-有点疑问

hitcser01

前提:
设 p[i ] 存储长度为 i 的钢条价格,
设 r[i ] 存储长度为 i 的钢条切割的最优解.

我的疑问:
为何 最优解是

1. p[i]+r[n-i]

复制代码

而不是

1. r[i]+r[n-i]

复制代码

呢?
如果得到最优解

1. p[i]+r[n-i]

复制代码

, 那么再对左侧的 i 钢条进行切割 可能有 r[i ] > p[i ] ,进而得到比最优解更优的解. 这个思路哪里错了?

谢谢!

automation_mb

应该是 r[n] = max{ p[i] + r[n-i] }
你指的对i再进行切割的情况，其实已被上述递归式囊括。

hitcser01

@automation_mb
嗯嗯,是的,谢谢.

如果对 i 再切割使得 i = k + j 有"更优解",则 r[n] = p[k] + r[n-k] 而不是 p[i ] + r[n-i] 了.