Це класична задача динамічного програмування, по суті — варіант задачі про розмін монет, тільки максимізуємо кількість частин.
Нехай — максимальна кількість частин, на яку можна розрізати стрічку довжини рівно . Значення позначає, що така довжина недосяжна.
База: \mathrm{dp}[0] = 0 — порожню стрічку розрізано на нуль частин.
Перехід: останній відрізаний шматок має довжину , або , тому
де беруться лише ті варіанти, для яких i \ge x і стан \mathrm{dp}[i-x] досяжний.
Відповідь — . Умова гарантує, що коректне розрізання існує, тому це значення не буде .
Складність — за часом і пам'яттю, що при N \le 4000 миттєво.
Зверніть увагу, що жадібний підхід (щоразу відрізати найкоротший шматок) тут не працює: він може привести до довжини, яку вже неможливо дорізати. Саме тому потрібна динаміка. Значення , , можуть збігатися — на алгоритм це ніяк не впливає.