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

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