CLRS устанавливает два эквивалентных способа формирования подзадач для задачи резки стержня:
r(n) = max(r(1) + r(n-1), r(2) + r(n-2),...,r(n-1) + r(1), p(n))
и
r(n) = max(p(1) + r(n-1), p(2) + r(n-2),...,p(n-1) + r(1), p(n))
, где r(i) - максимальный доход, возможный для резки стержня. длины i, а p(i) - цена стержня длиной i.
То, что я не могу понять, это то, как эти два эквивалента. Может ли кто-нибудь предоставить доказательство?