杆件切削问题的递推解法——动态规划

Question

Problem Statement: Given a rod of length n inches and an array of
prices that includes prices of all pieces of size smaller than n.
Determine the maximum value obtainable by cutting up the rod and
selling the pieces.

对于这个问题，我很困惑，为什么我到处都能看到这个问题的解决方案，即the maximum value of the Rod defined as

R[n] = Max (p[n], R[n-1] + P[1], R[n-2] + P[2] + ... P[1] + R[n-1]--1

而不是

R[n] = Max (p[n], R[n-1] + R[1], R[n-2] + R[2] + ... R[1] + R[n-1]--2

其中R[n]是指我们通过销售n个棒可以获得的最大收入

Base case as:
R[0] = some value
R[1] = somevalue

方程2更正确和恰当，因为在任何时候R[i]都不会小于p[i]。

我错过了什么？

Answer 1

两个方程给出的答案相同。从这个意义上说，他们中没有一个比另一个更正确。你喜欢哪一种是口味的问题。我发现等式1更直观一些。解决方案是最大限度地取下整个杆，或者切下一块长度为1的杆，其余的杆做得最好，或者切出一块长度2的杆，剩下的杆做的最好。。。