Робот идёт по клетчатому полю только вправо и вверх и собирает монеты. Как найти наибольшую добычу, не перебирая все пути?
Идея: считать по клеткам, а не по путям. В каждую клетку можно прийти только слева или снизу. Значит, лучшая добыча на пути к клетке равна её числу плюс большее из значений для соседа слева и соседа снизу.
Способ:
- В стартовую клетку впиши её число.
- Заполняй поле по рядам снизу вверх, слева направо: для каждой клетки — её число плюс максимум из клетки слева и клетки снизу (у края — тот сосед, который есть).
- Число в финишной клетке — ответ.
Так же можно посчитать количество путей: в каждую клетку ведёт столько путей, сколько в соседа слева и в соседа снизу вместе.
Чтобы найти сам лучший путь, пройди от финиша назад, каждый раз переходя к тому соседу, у которого значение больше.