Ніндзя складає свій тренувальний план на "N" днів, і кожного дня має вибір між трьома активностями: бігом, тренуванням бою або вивченням нових рухів. Кожна активність дає певну кількість балів, і мета Ніндзя — заробити максимальну кількість балів, при цьому не повторюючи одну й ту саму активність два дні поспіль.
Для вирішення цієї задачі ми маємо 2D масив, де кожен рядок містить бали для кожної з трьох активностей. Завдання — знайти максимальну кількість балів, яку Ніндзя може заробити, дотримуючись умови.
Ми можемо розглядати задачу як рекурсивну, де кожен крок буде залежати від попереднього. У кожному дні Ніндзя має вибір, яку активність виконати, і це впливає на його загальні бали. Для оптимального рішення можна застосувати підхід з меморизацією або табуляцією, щоб зменшити обчислювальну складність.
При розв'язанні задачі можна використовувати рекурсію з трьома можливими варіантами для кожного дня: вибір бігу, бою або вивчення нових рухів. Для кожного варіанту перевіряється, яку максимальну кількість балів можна отримати, враховуючи попередній день. Кожен крок буде залежати від попереднього, і вибір буде обмежений умовою, що не можна повторювати одну й ту саму активність двічі поспіль.
Щоб оптимізувати рішення, можна використовувати 2D масив для збереження результатів на кожному етапі, або скоротити простір до одного масиву для попереднього і поточного дня, якщо використовувати оптимізацію простору.
Задача можна вирішити за допомогою рекурсії, меморизації або табуляції, в залежності від того, як ефективно хочемо обробляти дані. Часова складність буде залежати від використаного методу, але всі варіанти забезпечують розв'язок, який працює швидко навіть для великих розмірів даних.
Перекладено з: Ninjas Training Coding Problem