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

(Е. Джобс) Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое по-ложительное число – количество монет. Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначены жирной линией, через которые Сборщик проходить не может. Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней. Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной?
Исходные данные для Робота записаны в файле 18-115.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата. В ответе укажите сначала максимальный, затем минимальный результат, который может быть получен исполнителем.