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