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

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