3 Главная идея — таблица сумм
Главная идея — таблица сумм
Робот приходит в клетку либо сверху, либо слева. Значит, наибольшая сумма в клетке — это её монета плюс больший из двух соседей (сверху или слева), в которых сумма уже посчитана. Заполняем поле сумм слева направо и сверху вниз — и в конечной клетке получаем ответ.
Слева — исходное поле с монетами (жирные линии — стены). Справа — таблица сумм: в каждой клетке записана наибольшая сумма, с которой в неё можно прийти. В правой нижней клетке — 25, это и есть максимум.
Формула для каждой клетки:
Сумма = монета + максимум( сумма сверху , сумма слева )
Верхняя левая клетка (старт) = просто её монета.
Верхняя строка: приходить можно только слева → монета + сосед слева.
Левый столбец: только сверху → монета + сосед сверху.
📌 Стена «отрезает» соседа Если между клеткой и соседом стоит стена, из этого соседа прийти нельзя — в формуле его не учитываем. Если стена слева — берём только соседа сверху; если сверху — только слева. Если клетка отрезана с двух сторон — в неё Робот не попадёт. |