7.3 Пути в решётке¶

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

Рассмотрим пример.

Один из оптимальных путей может выглядеть так:

(1,1) → (1,2) → (2,2) → (2,3) → (3,3) → (4,3) → (4,4) → (5,4) → (5,5)

Сумма по этому пути равна:

Как здесь появляется динамическое программирование¶

Пронумеруем строки и столбцы от 1 до n. Пусть value[y][x] — число в клетке (y, x).

Определим функцию:

— это максимальная сумма на пути из левого верхнего угла в клетку (y, x).

Тогда ответом для всей задачи будет:

Например, в таблице выше итоговый ответ — это sum(5, 5) = 55.

Рекуррентная формула¶

В клетку (y, x) можно попасть только двумя способами:

• из клетки слева (y, x-1);
• из клетки сверху (y-1, x).

Поэтому оптимальное значение вычисляется так:

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

Наглядно переход выглядит так:

flowchart LR
    A["sum(y, x-1)"] --> C["sum(y, x)"]
    B["sum(y-1, x)"] --> C

Граничные случаи¶

Чтобы формула работала единообразно, удобно считать, что за пределами таблицы путей нет. На практике это обычно оформляют отдельно:

• sum(1, 1) = value[1][1];
• для первой строки можно приходить только слева;
• для первого столбца можно приходить только сверху.

Другой вариант — завести массив с нулевой рамкой и аккуратно обработать стартовую клетку отдельно.

Реализация через двумерный массив¶

Так как функция зависит от двух параметров, массив динамики тоже будет двумерным:

int dp[N][N];

Тогда вычисление значений можно выполнить двойным циклом:

for (int y = 1; y <= n; y++) {
    for (int x = 1; x <= n; x++) {
        if (y == 1 && x == 1) {
            dp[y][x] = value[y][x];
        } else if (y == 1) {
            dp[y][x] = dp[y][x - 1] + value[y][x];
        } else if (x == 1) {
            dp[y][x] = dp[y - 1][x] + value[y][x];
        } else {
            dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]) + value[y][x];
        }
    }
}

После этого ответ находится в dp[n][n].

Полный пример на C++¶

#include <bits/stdc++.h>
using namespace std;

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

    vector<vector<int>> value(n + 1, vector<int>(n + 1));
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= n; x++) {
            cin >> value[y][x];
        }
    }

    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= n; x++) {
            if (y == 1 && x == 1) {
                dp[y][x] = value[y][x];
            } else if (y == 1) {
                dp[y][x] = dp[y][x - 1] + value[y][x];
            } else if (x == 1) {
                dp[y][x] = dp[y - 1][x] + value[y][x];
            } else {
                dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]) + value[y][x];
            }
        }
    }

    cout << dp[n][n] << "\n";
    return 0;
}

Как восстановить сам путь¶

Иногда нужно не только узнать максимальную сумму, но и восстановить маршрут. Для этого можно идти назад из клетки (n, n):

• если dp[y][x] получено из dp[y][x-1], значит мы пришли слева;
• если из dp[y-1][x], значит мы пришли сверху.

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

Оценка сложности¶

В таблице n × n ровно n^2 клеток, и для каждой мы делаем O(1) действий. Значит:

— время работы,

— память для массива динамики.

Чтобы найти лучший путь до клетки, достаточно знать лучший путь до клетки слева и сверху. Именно это и делает задачу классическим примером динамического программирования по таблице.