Найти цену для резки стержня

Question

Указанная длина стержня и P (цена) для первых 3 стержней. Мы должны заполнить возможную цену, которую мы можем получить для остальных стержней. Предполагая, что мы можем отрезать длинные куски по мере необходимости.

L = 1  2  3  4  5  6   7   8 
p = 3  8  12 

Мы в основном хотим получить максимальную цену, которую мы можем получить за каждую недостающую длину.

Мой подход Я считаю, что, так как мы дали наилучшую цену для стержня длиной 1,2 и 3 мы можем сгенерировать все возможные комбинации для следующих стержней.

For example to get price of rod where L = 4 
price of rod where L = 1 + rod where L = 3 = 15 
price of rod where L = 2 + rode where L = 2 = 16 
Therefore price of rod wehre L = 4 = 16 since 16 > 15. 

For example to get price of rod where L = 5 
price of rod where L = 1 + rod where L = 2 and rod where L = 2 = 19 
price of rod where L = 3 + rod where L = 2 = 20 
price of rod where L = 4 + rod where L = 1 = 19 

Так что это своего рода подход, которым я следую. Однако я не уверен, что я прав. Мне также хотелось бы, чтобы кто-то мог проверить этот подход, а также, может быть, помочь мне получить формулу из этого. Я не ищу код, так как понимания проблемы достаточно, чтобы написать код.

Answer 1

Вы можете проверить объяснение изменения этой проблемы в CLRS (раздел 15.1, страница 360). Проблема называется проблемой резания стержня.

Ваш подход правильный, и вы можете его формализовать как отношение повторения.

f(n) = min(f(n - i) + price(i)). 1 <= i <= n - 1 

f(n) где это минимальная цена, чтобы купить стержень длины п. с использованием memoization, это может быть рассчитано в O(n^2).