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

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