Задание №18: Динамическое программирование (Робот в таблице)

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки верхней строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в одну из трёх соседних клеток следующей строки: вниз, вниз и влево или вниз и вправо. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите маршрут Робота, при котором он соберёт максимальную денежную сумму.
Исходные данные записаны в файле 18-166.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: максимальную возможную денежную сумму, которую может собрать Робот, затем количество собранных при этом монет с чётным значением.