Стародавній замок має форму
квадрата й містить N x N кімнат. У кожній кімнаті
розставлені скриньки із золотими монетами. Буратіно знаходиться у верхній лівій
кімнаті й мріє, зібравши якомога більше монет, дістатись до правої нижньої
кімнати. З кожної кімнати він може перейти до сусідньої знизу або сусідньої
праворуч. Ви також хочете запам’ятати маршрут, який пройде Буратіно.
Ідея розв’язання. Задача є
класичною задачею динамічного програмування. Розглянути всі можливі маршрути
майже нереально. Тому подамо замок у вигляді двовимірного масиву, у кожну
клітинку якого запишемо кількість монет у відповідній кімнаті. За умовою
загальна кількість монет повинна бути максимальною, а це значить, що вона
повинна бути максимальною як на усьому маршруті, так і на кожній ділянці. Тому
заведемо ще один двовимірний масив, у якому будемо записувати максимальні
значення при виборі із двох можливих кімнат.
Малюнок, який ілюструє роботу програми для випадку N=5