Задача C++, динамическое программирование

Минимальный путь в таблице

В прямоугольной таблице N × M (в каждой клетке которой записано некоторое число) вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую, игрок может попасть в правый нижний угол, а также путь игрока.

Входные данные

Во входных данных задано два числа N и M – размеры таблицы (1 ≤ N ≤ 20, 1 ≤ M ≤ 20). Затем идет N строк по M чисел в каждой – размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные

В первой строке выведите минимальную сумму, потратив которую, можно попасть в правый нижний угол.

После этого выведите строку, описывающую путь игрока. Строка должна содержать только символы R и D. Символ R говорит о том, что на очередном шаге надо пойти вправо, а символ D – вниз. В случае нескольких верных ответов выведите любой.

ограничение по времени на тест

1 секунда

ограничение по памяти на тест

256 мегабайт