Вариант резки стержня

Вам дается деревянная палка длиной X с метками m в произвольных местах (неотъемлемая часть), и маркировка подсказывает, где должны быть надрезы сделал соответственно. За разрезание палки длиной L на две части плотник взимает L долларов (независимо от того, имеют ли эти две части одинаковой длины, т. Е. Стоимость измельчения не зависит от того, где находится точка измельчения) . Разработайте алгоритм динамического программирования, рассчитывающий минимальную общую стоимость.

Не удалось определить повторение. Меня спросили об этом в недавнем интервью по программированию.