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

(А. Богданов) Исходные данные для Робота записаны в файле 18-0.xls в виде электронной таблицы прямоугольной формы. Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки верхней строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в следующий ряд и может за одно перемещение попасть в одну из трех клеток следующей строки (на клетку прямо или боковые с ней). Ходы только в бок (без смены строки) и/или назад запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя с северной границы поля (сверху) до южной границы поля (снизу). В ответе укажите два числа; сначала максимальную сумму, затем минимальную.