1. Идея

Нужно найти путь из левой верхней клетки в правую нижнюю, двигаясь только вправо и вниз, чтобы сумма монет на посещённых клетках была максимальной.

Это классическая задача на динамическое программирование по таблице.

Будем считать dp[i][j] — максимальное число монет, которое можно собрать, если прийти в клетку (i, j).

Тогда в клетку (i, j) можно попасть только:

• сверху, из (i - 1, j);
• слева, из (i, j - 1).

Значит, выгоднее прийти из той клетки, у которой значение dp больше.

Кроме самой максимальной суммы, нужно восстановить путь. Для этого в отдельной таблице будем хранить, откуда мы пришли в каждую клетку:

• 'D', если пришли сверху;
• 'R', если пришли слева.

После заполнения таблицы можно пройти назад из правой нижней клетки в левую верхнюю и восстановить ответ.

2. Наблюдения

Наблюдение 1

В первую клетку (0, 0) робот уже находится в начале, значит:

• dp[0][0] = a[0][0]

Наблюдение 2

В клетках первой строки можно двигаться только вправо, значит туда можно прийти только слева.

Поэтому для i = 0:

• dp[0][j] = dp[0][j - 1] + a[0][j]

и предыдущий ход — 'R'.

Наблюдение 3

В клетках первого столбца можно двигаться только вниз, значит туда можно прийти только сверху.

Поэтому для j = 0:

• dp[i][0] = dp[i - 1][0] + a[i][0]

и предыдущий ход — 'D'.

Наблюдение 4

Для любой внутренней клетки есть ровно два варианта перехода:

• сверху;
• слева.

Значит:

• если dp[i - 1][j] >= dp[i][j - 1], выгоднее прийти сверху;
• иначе — слева.

Равенство тоже допустимо: по условию нужно вывести любой оптимальный путь. В эталонном решении при равенстве выбирается приход сверху.

Наблюдение 5

Когда мы записываем в prev_move[i][j] символ:

• 'D' — это значит, что в клетку (i, j) пришли сверху, то есть последним движением был шаг вниз;
• 'R' — это значит, что пришли слева, то есть последним движением был шаг вправо.

При восстановлении пути идём из конца в начало, поэтому:

• если видим 'D', поднимаемся на строку вверх;
• если видим 'R', сдвигаемся влево.

3. Алгоритм

1. Считываем m и n.
2. Создаём:
   • таблицу dp размера m x n, где храним максимальную сумму монет;
   • таблицу prev_move размера m x n, где храним предыдущий ход для восстановления ответа.
3. Последовательно читаем все клетки сетки и сразу заполняем dp:
   • для (0, 0) записываем значение монет;
   • для первой строки берём значение слева;
   • для первого столбца берём значение сверху;
   • для остальных клеток выбираем максимум из двух вариантов.
4. После этого находим путь:
   • начинаем из клетки (m - 1, n - 1);
   • пока не пришли в (0, 0), смотрим prev_move[i][j];
   • добавляем этот символ в ответ;
   • если это 'D', уменьшаем i;
   • иначе уменьшаем j.
5. Путь получится в обратном порядке, поэтому разворачиваем его.
6. Выводим результат.

4. Почему это работает

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

Рассмотрим клетку (i, j).

Чтобы попасть в неё, робот может сделать только один из двух последних шагов:

• вниз из клетки (i - 1, j);
• вправо из клетки (i, j - 1).

Других способов нет, потому что двигаться можно только вправо и вниз.

Пусть dp[i][j] — максимальная сумма монет на пути до клетки (i, j).

Тогда оптимальный путь в (i, j) обязательно должен состоять из:

• оптимального пути в одну из допустимых предыдущих клеток;
• плюс монеты в текущей клетке.

Иначе, если бы путь в предыдущую клетку был не оптимален, его можно было бы заменить на лучший и получить более выгодный путь в (i, j), что противоречит оптимальности.

Значит, переход верен:

• dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]

для внутренних клеток.

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

Таким образом, после заполнения всей таблицы dp[m - 1][n - 1] будет равна максимальному числу монет, которое можно собрать на пути в правую нижнюю клетку.

Теперь о восстановлении пути.

Для каждой клетки мы запоминаем, откуда в неё пришли в оптимальном варианте:

• сверху или слева.

Если из конечной клетки идти назад по этим указателям, мы получим некоторый путь до начала. Поскольку указатель в каждой клетке соответствует именно тому переходу, который использовался при вычислении оптимального dp, восстановленный путь тоже будет оптимальным.

Следовательно, алгоритм корректен.

5. Сложность

Пусть всего в таблице m * n клеток.

Время

Мы один раз обрабатываем каждую клетку и выполняем в ней O(1) действий.

Итоговая сложность:

• O(m * n)

Восстановление пути занимает O(m + n), что меньше основного времени.

Память

Храним две таблицы размера m x n:

• dp
• prev_move

Итоговая сложность по памяти:

• O(m * n)

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<long long>> dp(m, vector<long long>(n));
    vector<vector<char>> prev_move(m, vector<char>(n, 0));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            long long x;
            cin >> x;

            if (i == 0 && j == 0) {
                dp[i][j] = x;
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] + x;
                prev_move[i][j] = 'R';
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] + x;
                prev_move[i][j] = 'D';
            } else {
                if (dp[i - 1][j] >= dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j] + x;
                    prev_move[i][j] = 'D';
                } else {
                    dp[i][j] = dp[i][j - 1] + x;
                    prev_move[i][j] = 'R';
                }
            }
        }
    }

    string path;
    int i = m - 1;
    int j = n - 1;

    while (i > 0 || j > 0) {
        char c = prev_move[i][j];
        path.push_back(c);
        if (c == 'D') {
            i--;
        } else {
            j--;
        }
    }

    reverse(path.begin(), path.end());
    cout << path << '\n';

    return 0;
}

7. Код на Python 3

m, n = map(int, input().split())

dp = [[0] * n for _ in range(m)]
prev_move = [[''] * n for _ in range(m)]

for i in range(m):
    row = list(map(int, input().split()))
    for j in range(n):
        x = row[j]
        if i == 0 and j == 0:
            dp[i][j] = x
        elif i == 0:
            dp[i][j] = dp[i][j - 1] + x
            prev_move[i][j] = 'R'
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + x
            prev_move[i][j] = 'D'
        else:
            if dp[i - 1][j] >= dp[i][j - 1]:
                dp[i][j] = dp[i - 1][j] + x
                prev_move[i][j] = 'D'
            else:
                dp[i][j] = dp[i][j - 1] + x
                prev_move[i][j] = 'R'

path = []
i = m - 1
j = n - 1

while i > 0 or j > 0:
    c = prev_move[i][j]
    path.append(c)
    if c == 'D':
        i -= 1
    else:
        j -= 1

path.reverse()
print(''.join(path))