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

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