Продажа ленты по кускам
Задача по программированию с проверкой онлайн
- Сложность
- Лёгкая
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
В магазине есть лента длиной n метров, где n — длина списка prices. Кусок целой длины k метров продаётся за prices[k - 1], цены неотрицательны и не обязаны расти с длиной. Ленту можно разрезать на любое число кусков целой длины или продать целиком, остатков нет. Верните наибольшую выручку. Для пустого списка ответ 0. Ограничения: до 40 метров.
Подумайте, какой кусок отрезать первым: после него остаётся лента меньшей длины, для которой тот же вопрос уже решён.
Пример: [1, 5, 8, 9] → 10 (два куска по 2 метра: 5 + 5).
Источник: задача CodeShare
Решить онлайнБесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).