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

(М. Коротков) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 15. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите:

A) максимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю;
B) количество различных маршрутов из левой нижней клетки в правую верхнюю, каждый из которых позволяет Роботу собрать денежную сумму из п. А.

Исходные данные для Робота записаны в файле 18-114.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала ответ на вопрос А, затем – ответ на вопрос B.