Условие задачи: Вам дана прямоугольная матрица matrix размера n×m, где каждая ячейка содержит число – стоимость прохождения через неё. Черепашка стартует в клетке (0, 0) и может перемещаться только вправо или вниз. Необходимо найти путь от клетки (0, 0) до (n-1, m-1) с минимальной суммарной стоимостью и вывести последовательность шагов.

Формат входных данных: В первой строке заданы два числа n и m (1 ≤ n, m ≤ 1000). Далее следуют n строк, каждая из которых содержит m целых чисел церез пробел, где 0 ≤ matrix[i][j] ≤ 100.

Формат выходных данных: В первой строке выведите минимальную суммарную стоимость, а во второй — последовательность символов R (вправо) и D (вниз), обозначающих шаги черепашки (например: RRDRD).

Решение: Для решения задачи применяется метод динамического программирования. Создаётся двумерный массив dp, где dp[i][j] означает минимальную стоимость пути от клетки (0,0) до клетки (i,j). Дополнительно формируется массив parent для восстановления маршрута, где parent[i][j] хранит информацию о направлении предыдущего шага ('R' — если переход был выполнен из левой ячейки, и 'D' — если из верхней).

Начальное условие:

dp[0][0] = matrix[0][0]

Для остальных ячеек выбираем оптимальный переход — из ячейки сверху или слева, одновременно обновляя предка текущей ячейки:

После заполнения массива dp значение dp[n-1][m-1] является искомой минимальной стоимостью, а массив parent позволяет восстановить оптимальный путь.

Например, если дана матрица:

то после вычислений получим:

Восстановление пути: Начните с клетки (n-1, m-1) и, следуя указателям массива parent, вернитесь к клетке (0, 0). Полученная последовательность шагов затем разворачивается для вывода оптимального маршрута.