Перейти к содержанию

14.3   Подход к решению задач динамического программирования

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

  1. Как определить, является ли некоторая задача задачей динамического программирования?
  2. С чего начинать решение такой задачи и как выглядит полный процесс решения?

14.3.1   Определение задачи

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

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

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

Поверх этого у задач динамического программирования есть и некоторые дополнительные "плюсы".

  • В условии задачи фигурируют слова "максимальный", "минимальный", "наибольший", "наименьший" и другие формулировки оптимизации.
  • Состояния задачи можно описать списком, многомерной матрицей или деревом, и между состоянием и соседними состояниями существует рекуррентная зависимость.

Соответственно, существуют и некоторые "минусы".

  • Цель задачи состоит в поиске всех возможных решений, а не одного оптимального решения.
  • В формулировке явно присутствуют признаки комбинаторного перечисления, и требуется вернуть сразу много конкретных вариантов.

Если задача удовлетворяет модели дерева решений и имеет достаточно явные "плюсы", мы можем предположить, что это задача динамического программирования, а затем проверить это предположение уже в процессе решения.

14.3.2   Этапы решения задачи

Конкретный процесс решения задач динамического программирования зависит от природы и сложности задачи, но обычно включает следующие шаги: описание решений, определение состояний, построение таблицы \(dp\) , вывод уравнения перехода состояния, определение граничных условий и порядка переходов.

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

Question

Дана двумерная сетка grid размера \(n \times m\) , в каждой клетке которой записано неотрицательное целое число, означающее стоимость прохождения через эту клетку. Робот стартует из левой верхней клетки и за один шаг может двигаться только вправо или вниз, пока не достигнет правой нижней клетки. Верните минимальную сумму пути от левой верхней клетки до правой нижней.

На рисунке 14-10 показан пример, в котором минимальная сумма пути равна \(13\) .

Пример данных для задачи о минимальной сумме пути

Рисунок 14-10   Пример данных для задачи о минимальной сумме пути

Шаг 1: понять решения на каждом раунде, определить состояние и тем самым получить таблицу \(dp\)

В этой задаче на каждом раунде решение состоит в том, чтобы из текущей клетки сделать один шаг вниз или вправо. Пусть индексы строки и столбца текущей клетки равны \([i, j]\) ; тогда после шага вниз или вправо индексы становятся равными \([i+1, j]\) или \([i, j+1]\) . Значит, состояние должно включать два переменных индекса: строки и столбца, то есть состояние обозначается как \([i, j]\) .

Подзадача, соответствующая состоянию \([i, j]\) , такова: минимальная сумма пути от стартовой клетки \([0, 0]\) до клетки \([i, j]\) . Ее решение обозначается через \(dp[i, j]\) .

На этом этапе мы получаем двумерную матрицу \(dp\) , показанную на рисунке 14-11, размер которой совпадает с размером входной сетки grid .

Определение состояния и таблицы dp

Рисунок 14-11   Определение состояния и таблицы dp

Note

Как в динамическом программировании, так и в backtracking, решение задачи можно описать как последовательность решений, а состояние образуется всеми переменными решений. Оно должно содержать всю информацию, достаточную для вывода следующего состояния.

Каждому состоянию соответствует некоторая подзадача, и для хранения решений всех подзадач мы определяем таблицу \(dp\) ; каждая независимая переменная состояния становится одним измерением таблицы \(dp\) . По сути таблица \(dp\) - это отображение от состояния к решению соответствующей подзадачи.

Шаг 2: найти оптимальную подструктуру и на ее основе вывести уравнение перехода состояния

Для состояния \([i, j]\) возможны только два источника: клетка сверху \([i-1, j]\) и клетка слева \([i, j-1]\) . Следовательно, оптимальная подструктура выглядит так: минимальная сумма пути до \([i, j]\) определяется меньшим из двух значений - минимальной суммы пути до \([i-1, j]\) и минимальной суммы пути до \([i, j-1]\) .

По этому рассуждению получается уравнение перехода состояния, показанное на рисунке 14-12:

\[ dp[i, j] = \min(dp[i-1, j], dp[i, j-1]) + grid[i, j] \]

Оптимальная подструктура и уравнение перехода состояния

Рисунок 14-12   Оптимальная подструктура и уравнение перехода состояния

Note

Опираясь на уже определенную таблицу \(dp\) , нужно продумать отношение между исходной задачей и подзадачами и найти способ построить оптимальное решение исходной задачи из оптимальных решений подзадач, то есть найти оптимальную подструктуру.

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

Шаг 3: определить граничные условия и порядок переходов

В этой задаче состояния в первой строке могут переходить только из клетки слева, а состояния в первом столбце - только из клетки сверху, поэтому первая строка \(i = 0\) и первый столбец \(j = 0\) образуют граничные условия.

Как показано на рисунке 14-13, поскольку каждая клетка получается из клетки слева и клетки сверху, мы можем проходить матрицу циклами: внешний цикл по строкам, внутренний - по столбцам.

Граничные условия и порядок перехода состояний

Рисунок 14-13   Граничные условия и порядок перехода состояний

Note

В динамическом программировании граничные условия используются для инициализации таблицы \(dp\) , а в поиске - для обрезки.

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

После этого анализа мы уже можем напрямую написать код динамического программирования. Однако разложение на подзадачи - это мышление "сверху вниз", поэтому с точки зрения мышления более естественно реализовывать задачу в порядке "полный перебор \(\rightarrow\) поиск с мемоизацией \(\rightarrow\) динамическое программирование".

1.   Метод 1: полный перебор

Начав со состояния \([i, j]\) , мы непрерывно раскладываем его на меньшие состояния \([i-1, j]\) и \([i, j-1]\) . Рекурсивная функция при этом имеет следующие элементы.

  • Параметры рекурсии: состояние \([i, j]\) .
  • Возвращаемое значение: минимальная сумма пути до \([i, j]\) , то есть \(dp[i, j]\) .
  • Условие завершения: когда \(i = 0\) и \(j = 0\) , возвращается стоимость \(grid[0, 0]\) .
  • Обрезка: если \(i < 0\) или \(j < 0\) , индекс выходит за границы, и в этом случае возвращается стоимость \(+\infty\) , обозначающая невозможность.

Код реализации:

min_path_sum.py
def min_path_sum_dfs(grid: list[list[int]], i: int, j: int) -> int:
    """Минимальная сумма пути: полный перебор"""
    # Если это верхняя левая ячейка, завершить поиск
    if i == 0 and j == 0:
        return grid[0][0]
    # Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 or j < 0:
        return inf
    # Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    up = min_path_sum_dfs(grid, i - 1, j)
    left = min_path_sum_dfs(grid, i, j - 1)
    # Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return min(left, up) + grid[i][j]
min_path_sum.cpp
/* Минимальная сумма пути: полный перебор */
int minPathSumDFS(vector<vector<int>> &grid, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
}
min_path_sum.java
/* Минимальная сумма пути: полный перебор */
int minPathSumDFS(int[][] grid, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return Math.min(left, up) + grid[i][j];
}
min_path_sum.cs
/* Минимальная сумма пути: полный перебор */
int MinPathSumDFS(int[][] grid, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return int.MaxValue;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    int up = MinPathSumDFS(grid, i - 1, j);
    int left = MinPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return Math.Min(left, up) + grid[i][j];
}
min_path_sum.go
/* Минимальная сумма пути: полный перебор */
func minPathSumDFS(grid [][]int, i, j int) int {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0 && j == 0 {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return math.MaxInt
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    up := minPathSumDFS(grid, i-1, j)
    left := minPathSumDFS(grid, i, j-1)
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return int(math.Min(float64(left), float64(up))) + grid[i][j]
}
min_path_sum.swift
/* Минимальная сумма пути: полный перебор */
func minPathSumDFS(grid: [[Int]], i: Int, j: Int) -> Int {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0, j == 0 {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return .max
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    let up = minPathSumDFS(grid: grid, i: i - 1, j: j)
    let left = minPathSumDFS(grid: grid, i: i, j: j - 1)
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return min(left, up) + grid[i][j]
}
min_path_sum.js
/* Минимальная сумма пути: полный перебор */
function minPathSumDFS(grid, i, j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i === 0 && j === 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Infinity;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    const up = minPathSumDFS(grid, i - 1, j);
    const left = minPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return Math.min(left, up) + grid[i][j];
}
min_path_sum.ts
/* Минимальная сумма пути: полный перебор */
function minPathSumDFS(
    grid: Array<Array<number>>,
    i: number,
    j: number
): number {
    // Если это верхняя левая ячейка, завершить поиск
    if (i === 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Infinity;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    const up = minPathSumDFS(grid, i - 1, j);
    const left = minPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return Math.min(left, up) + grid[i][j];
}
min_path_sum.dart
/* Минимальная сумма пути: полный перебор */
int minPathSumDFS(List<List<int>> grid, int i, int j) {
  // Если это верхняя левая ячейка, завершить поиск
  if (i == 0 && j == 0) {
    return grid[0][0];
  }
  // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
  if (i < 0 || j < 0) {
    // В Dart тип int — целое число фиксированного диапазона; значения, представляющего «бесконечность», не существует
    return BigInt.from(2).pow(31).toInt();
  }
  // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
  int up = minPathSumDFS(grid, i - 1, j);
  int left = minPathSumDFS(grid, i, j - 1);
  // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
  return min(left, up) + grid[i][j];
}
min_path_sum.rs
/* Минимальная сумма пути: полный перебор */
fn min_path_sum_dfs(grid: &Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0 && j == 0 {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return i32::MAX;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    let up = min_path_sum_dfs(grid, i - 1, j);
    let left = min_path_sum_dfs(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    std::cmp::min(left, up) + grid[i as usize][j as usize]
}
min_path_sum.c
/* Минимальная сумма пути: полный перебор */
int minPathSumDFS(int grid[MAX_SIZE][MAX_SIZE], int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
}
min_path_sum.kt
/* Минимальная сумма пути: полный перебор */
fun minPathSumDFS(grid: Array<IntArray>, i: Int, j: Int): Int {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Int.MAX_VALUE
    }
    // Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
    val up = minPathSumDFS(grid, i - 1, j)
    val left = minPathSumDFS(grid, i, j - 1)
    // Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    return min(left, up) + grid[i][j]
}
min_path_sum.rb
### Минимальная сумма пути: полный перебор ###
def min_path_sum_dfs(grid, i, j)
  # Если это верхняя левая ячейка, завершить поиск
  return grid[i][j] if i == 0 && j == 0
  # Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
  return Float::INFINITY if i < 0 || j < 0
  # Вычислить минимальную стоимость пути из левого верхнего угла до (i-1, j) и (i, j-1)
  up = min_path_sum_dfs(grid, i - 1, j)
  left = min_path_sum_dfs(grid, i, j - 1)
  # Вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
  [left, up].min + grid[i][j]
end
Визуализация кода

На рисунке 14-14 показано дерево рекурсии с корнем в \(dp[2, 1]\) ; в нем содержатся перекрывающиеся подзадачи, и их число будет резко расти вместе с размером сетки grid .

По своей сути причина появления перекрывающихся подзадач такова: существует много разных путей от левого верхнего угла до одной и той же клетки.

Дерево рекурсии полного перебора

Рисунок 14-14   Дерево рекурсии полного перебора

У каждого состояния есть два выбора - вниз и вправо, а от левого верхнего угла до правого нижнего нужно сделать всего \(m + n - 2\) шагов, поэтому худшая временная сложность равна \(O(2^{m + n})\) , где \(n\) и \(m\) - число строк и столбцов сетки соответственно. Заметим, что в этой оценке не учитывается близость к границам сетки: у граничных клеток остается только один выбор, так что фактическое число путей будет несколько меньше.

2.   Метод 2: поиск с мемоизацией

Введем список памяти mem того же размера, что и сетка grid , для хранения решений всех подзадач и отсечения перекрывающихся подзадач:

min_path_sum.py
def min_path_sum_dfs_mem(
    grid: list[list[int]], mem: list[list[int]], i: int, j: int
) -> int:
    """Минимальная сумма пути: поиск с мемоизацией"""
    # Если это верхняя левая ячейка, завершить поиск
    if i == 0 and j == 0:
        return grid[0][0]
    # Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 or j < 0:
        return inf
    # Если запись уже есть, вернуть сразу
    if mem[i][j] != -1:
        return mem[i][j]
    # Минимальная стоимость пути для левой и верхней ячеек
    up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
    left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
    # Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = min(left, up) + grid[i][j]
    return mem[i][j]
min_path_sum.cpp
/* Минимальная сумма пути: поиск с мемоизацией */
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}
min_path_sum.java
/* Минимальная сумма пути: поиск с мемоизацией */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}
min_path_sum.cs
/* Минимальная сумма пути: поиск с мемоизацией */
int MinPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return int.MaxValue;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    int up = MinPathSumDFSMem(grid, mem, i - 1, j);
    int left = MinPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = Math.Min(left, up) + grid[i][j];
    return mem[i][j];
}
min_path_sum.go
/* Минимальная сумма пути: поиск с мемоизацией */
func minPathSumDFSMem(grid, mem [][]int, i, j int) int {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0 && j == 0 {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return math.MaxInt
    }
    // Если запись уже есть, вернуть сразу
    if mem[i][j] != -1 {
        return mem[i][j]
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    up := minPathSumDFSMem(grid, mem, i-1, j)
    left := minPathSumDFSMem(grid, mem, i, j-1)
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = int(math.Min(float64(left), float64(up))) + grid[i][j]
    return mem[i][j]
}
min_path_sum.swift
/* Минимальная сумма пути: поиск с мемоизацией */
func minPathSumDFSMem(grid: [[Int]], mem: inout [[Int]], i: Int, j: Int) -> Int {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0, j == 0 {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return .max
    }
    // Если запись уже есть, вернуть сразу
    if mem[i][j] != -1 {
        return mem[i][j]
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    let up = minPathSumDFSMem(grid: grid, mem: &mem, i: i - 1, j: j)
    let left = minPathSumDFSMem(grid: grid, mem: &mem, i: i, j: j - 1)
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = min(left, up) + grid[i][j]
    return mem[i][j]
}
min_path_sum.js
/* Минимальная сумма пути: поиск с мемоизацией */
function minPathSumDFSMem(grid, mem, i, j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i === 0 && j === 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Infinity;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] !== -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    const up = minPathSumDFSMem(grid, mem, i - 1, j);
    const left = minPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}
min_path_sum.ts
/* Минимальная сумма пути: поиск с мемоизацией */
function minPathSumDFSMem(
    grid: Array<Array<number>>,
    mem: Array<Array<number>>,
    i: number,
    j: number
): number {
    // Если это верхняя левая ячейка, завершить поиск
    if (i === 0 && j === 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Infinity;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    const up = minPathSumDFSMem(grid, mem, i - 1, j);
    const left = minPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = Math.min(left, up) + grid[i][j];
    return mem[i][j];
}
min_path_sum.dart
/* Минимальная сумма пути: поиск с мемоизацией */
int minPathSumDFSMem(List<List<int>> grid, List<List<int>> mem, int i, int j) {
  // Если это верхняя левая ячейка, завершить поиск
  if (i == 0 && j == 0) {
    return grid[0][0];
  }
  // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
  if (i < 0 || j < 0) {
    // В Dart тип int — целое число фиксированного диапазона; значения, представляющего «бесконечность», не существует
    return BigInt.from(2).pow(31).toInt();
  }
  // Если запись уже есть, вернуть сразу
  if (mem[i][j] != -1) {
    return mem[i][j];
  }
  // Минимальная стоимость пути для левой и верхней ячеек
  int up = minPathSumDFSMem(grid, mem, i - 1, j);
  int left = minPathSumDFSMem(grid, mem, i, j - 1);
  // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
  mem[i][j] = min(left, up) + grid[i][j];
  return mem[i][j];
}
min_path_sum.rs
/* Минимальная сумма пути: поиск с мемоизацией */
fn min_path_sum_dfs_mem(grid: &Vec<Vec<i32>>, mem: &mut Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
    // Если это верхняя левая ячейка, завершить поиск
    if i == 0 && j == 0 {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if i < 0 || j < 0 {
        return i32::MAX;
    }
    // Если запись уже есть, вернуть сразу
    if mem[i as usize][j as usize] != -1 {
        return mem[i as usize][j as usize];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    let up = min_path_sum_dfs_mem(grid, mem, i - 1, j);
    let left = min_path_sum_dfs_mem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i as usize][j as usize] = std::cmp::min(left, up) + grid[i as usize][j as usize];
    mem[i as usize][j as usize]
}
min_path_sum.c
/* Минимальная сумма пути: поиск с мемоизацией */
int minPathSumDFSMem(int grid[MAX_SIZE][MAX_SIZE], int mem[MAX_SIZE][MAX_SIZE], int i, int j) {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return INT_MAX;
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j];
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    int up = minPathSumDFSMem(grid, mem, i - 1, j);
    int left = minPathSumDFSMem(grid, mem, i, j - 1);
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = myMin(left, up) != INT_MAX ? myMin(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}
min_path_sum.kt
/* Минимальная сумма пути: поиск с мемоизацией */
fun minPathSumDFSMem(
    grid: Array<IntArray>,
    mem: Array<IntArray>,
    i: Int,
    j: Int
): Int {
    // Если это верхняя левая ячейка, завершить поиск
    if (i == 0 && j == 0) {
        return grid[0][0]
    }
    // Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
    if (i < 0 || j < 0) {
        return Int.MAX_VALUE
    }
    // Если запись уже есть, вернуть сразу
    if (mem[i][j] != -1) {
        return mem[i][j]
    }
    // Минимальная стоимость пути для левой и верхней ячеек
    val up = minPathSumDFSMem(grid, mem, i - 1, j)
    val left = minPathSumDFSMem(grid, mem, i, j - 1)
    // Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
    mem[i][j] = min(left, up) + grid[i][j]
    return mem[i][j]
}
min_path_sum.rb
### Минимальная сумма пути: поиск с мемоизацией ###
def min_path_sum_dfs_mem(grid, mem, i, j)
  # Если это верхняя левая ячейка, завершить поиск
  return grid[0][0] if i == 0 && j == 0
  # Если индексы строки или столбца выходят за границы, вернуть стоимость +∞
  return Float::INFINITY if i < 0 || j < 0
  # Если запись уже есть, вернуть сразу
  return mem[i][j] if mem[i][j] != -1
  # Минимальная стоимость пути для левой и верхней ячеек
  up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
  left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
  # Сохранить и вернуть минимальную стоимость пути из левого верхнего угла до (i, j)
  mem[i][j] = [left, up].min + grid[i][j]
end
Визуализация кода

Как показано на рисунке 14-15, после добавления мемоизации решение каждой подзадачи вычисляется только один раз, поэтому временная сложность определяется общим числом состояний, то есть равна \(O(nm)\) .

Дерево рекурсии для поиска с мемоизацией

Рисунок 14-15   Дерево рекурсии для поиска с мемоизацией

3.   Метод 3: динамическое программирование

Итеративная реализация динамического программирования выглядит так:

min_path_sum.py
def min_path_sum_dp(grid: list[list[int]]) -> int:
    """Минимальная сумма пути: динамическое программирование"""
    n, m = len(grid), len(grid[0])
    # Инициализация таблицы dp
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]
    # Переход состояний: первая строка
    for j in range(1, m):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    # Переход состояний: первый столбец
    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    # Переход состояний: остальные строки и столбцы
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
    return dp[n - 1][m - 1]
min_path_sum.cpp
/* Минимальная сумма пути: динамическое программирование */
int minPathSumDP(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // Инициализация таблицы dp
    vector<vector<int>> dp(n, vector<int>(m));
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}
min_path_sum.java
/* Минимальная сумма пути: динамическое программирование */
int minPathSumDP(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // Инициализация таблицы dp
    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}
min_path_sum.cs
/* Минимальная сумма пути: динамическое программирование */
int MinPathSumDP(int[][] grid) {
    int n = grid.Length, m = grid[0].Length;
    // Инициализация таблицы dp
    int[,] dp = new int[n, m];
    dp[0, 0] = grid[0][0];
    // Переход состояний: первая строка
    for (int j = 1; j < m; j++) {
        dp[0, j] = dp[0, j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (int i = 1; i < n; i++) {
        dp[i, 0] = dp[i - 1, 0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i, j] = Math.Min(dp[i, j - 1], dp[i - 1, j]) + grid[i][j];
        }
    }
    return dp[n - 1, m - 1];
}
min_path_sum.go
/* Минимальная сумма пути: динамическое программирование */
func minPathSumDP(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    // Инициализация таблицы dp
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
    }
    dp[0][0] = grid[0][0]
    // Переход состояний: первая строка
    for j := 1; j < m; j++ {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }
    // Переход состояний: первый столбец
    for i := 1; i < n; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    // Переход состояний: остальные строки и столбцы
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            dp[i][j] = int(math.Min(float64(dp[i][j-1]), float64(dp[i-1][j]))) + grid[i][j]
        }
    }
    return dp[n-1][m-1]
}
min_path_sum.swift
/* Минимальная сумма пути: динамическое программирование */
func minPathSumDP(grid: [[Int]]) -> Int {
    let n = grid.count
    let m = grid[0].count
    // Инициализация таблицы dp
    var dp = Array(repeating: Array(repeating: 0, count: m), count: n)
    dp[0][0] = grid[0][0]
    // Переход состояний: первая строка
    for j in 1 ..< m {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    // Переход состояний: первый столбец
    for i in 1 ..< n {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    // Переход состояний: остальные строки и столбцы
    for i in 1 ..< n {
        for j in 1 ..< m {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        }
    }
    return dp[n - 1][m - 1]
}
min_path_sum.js
/* Минимальная сумма пути: динамическое программирование */
function minPathSumDP(grid) {
    const n = grid.length,
        m = grid[0].length;
    // Инициализация таблицы dp
    const dp = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => 0)
    );
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for (let j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (let i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}
min_path_sum.ts
/* Минимальная сумма пути: динамическое программирование */
function minPathSumDP(grid: Array<Array<number>>): number {
    const n = grid.length,
        m = grid[0].length;
    // Инициализация таблицы dp
    const dp = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => 0)
    );
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for (let j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (let i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (let i = 1; i < n; i++) {
        for (let j: number = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}
min_path_sum.dart
/* Минимальная сумма пути: динамическое программирование */
int minPathSumDP(List<List<int>> grid) {
  int n = grid.length, m = grid[0].length;
  // Инициализация таблицы dp
  List<List<int>> dp = List.generate(n, (i) => List.filled(m, 0));
  dp[0][0] = grid[0][0];
  // Переход состояний: первая строка
  for (int j = 1; j < m; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  }
  // Переход состояний: первый столбец
  for (int i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }
  // Переход состояний: остальные строки и столбцы
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
      dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
    }
  }
  return dp[n - 1][m - 1];
}
min_path_sum.rs
/* Минимальная сумма пути: динамическое программирование */
fn min_path_sum_dp(grid: &Vec<Vec<i32>>) -> i32 {
    let (n, m) = (grid.len(), grid[0].len());
    // Инициализация таблицы dp
    let mut dp = vec![vec![0; m]; n];
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for j in 1..m {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for i in 1..n {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for i in 1..n {
        for j in 1..m {
            dp[i][j] = std::cmp::min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    dp[n - 1][m - 1]
}
min_path_sum.c
/* Минимальная сумма пути: динамическое программирование */
int minPathSumDP(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
    // Инициализация таблицы dp
    int **dp = malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        dp[i] = calloc(m, sizeof(int));
    }
    dp[0][0] = grid[0][0];
    // Переход состояний: первая строка
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // Переход состояний: первый столбец
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // Переход состояний: остальные строки и столбцы
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = myMin(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
        }
    }
    int res = dp[n - 1][m - 1];
    // Освободить память
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    return res;
}
min_path_sum.kt
/* Минимальная сумма пути: динамическое программирование */
fun minPathSumDP(grid: Array<IntArray>): Int {
    val n = grid.size
    val m = grid[0].size
    // Инициализация таблицы dp
    val dp = Array(n) { IntArray(m) }
    dp[0][0] = grid[0][0]
    // Переход состояний: первая строка
    for (j in 1..<m) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    // Переход состояний: первый столбец
    for (i in 1..<n) {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    // Переход состояний: остальные строки и столбцы
    for (i in 1..<n) {
        for (j in 1..<m) {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        }
    }
    return dp[n - 1][m - 1]
}
min_path_sum.rb
### Минимальная сумма пути: динамическое программирование ###
def min_path_sum_dp(grid)
  n, m = grid.length, grid.first.length
  # Инициализация таблицы dp
  dp = Array.new(n) { Array.new(m, 0) }
  dp[0][0] = grid[0][0]
  # Переход состояний: первая строка
  (1...m).each { |j| dp[0][j] = dp[0][j - 1] + grid[0][j] }
  # Переход состояний: первый столбец
  (1...n).each { |i| dp[i][0] = dp[i - 1][0] + grid[i][0] }
  # Переход состояний: остальные строки и столбцы
  for i in 1...n
    for j in 1...m
      dp[i][j] = [dp[i][j - 1], dp[i - 1][j]].min + grid[i][j]
    end
  end
  dp[n -1][m -1]
end
Визуализация кода

На рисунке 14-16 показан процесс переходов состояний в задаче о минимальной сумме пути. Он проходит по всей сетке, поэтому временная сложность равна \(O(nm)\) .

Размер массива dp равен \(n \times m\) , поэтому пространственная сложность равна \(O(nm)\) .

Процесс динамического программирования для минимальной суммы пути

min_path_sum_dp_step2

min_path_sum_dp_step3

min_path_sum_dp_step4

min_path_sum_dp_step5

min_path_sum_dp_step6

min_path_sum_dp_step7

min_path_sum_dp_step8

min_path_sum_dp_step9

min_path_sum_dp_step10

min_path_sum_dp_step11

min_path_sum_dp_step12

Рисунок 14-16   Процесс динамического программирования для минимальной суммы пути

4.   Оптимизация пространства

Поскольку каждая клетка зависит только от клетки слева и клетки сверху, таблицу \(dp\) можно реализовать с помощью одномерного массива, соответствующего одной строке.

Обратите внимание: поскольку массив dp теперь может представлять только одну строку состояний, мы не можем заранее инициализировать состояния первого столбца, а должны обновлять их по мере обхода каждой строки:

min_path_sum.py
def min_path_sum_dp_comp(grid: list[list[int]]) -> int:
    """Минимальная сумма пути: динамическое программирование с оптимизацией памяти"""
    n, m = len(grid), len(grid[0])
    # Инициализация таблицы dp
    dp = [0] * m
    # Переход состояний: первая строка
    dp[0] = grid[0][0]
    for j in range(1, m):
        dp[j] = dp[j - 1] + grid[0][j]
    # Переход состояний: остальные строки
    for i in range(1, n):
        # Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0]
        # Переход состояний: остальные столбцы
        for j in range(1, m):
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
    return dp[m - 1]
min_path_sum.cpp
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
int minPathSumDPComp(vector<vector<int>> &grid) {
    int n = grid.size(), m = grid[0].size();
    // Инициализация таблицы dp
    vector<int> dp(m);
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (int i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}
min_path_sum.java
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
int minPathSumDPComp(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    // Инициализация таблицы dp
    int[] dp = new int[m];
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (int i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (int j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}
min_path_sum.cs
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
int MinPathSumDPComp(int[][] grid) {
    int n = grid.Length, m = grid[0].Length;
    // Инициализация таблицы dp
    int[] dp = new int[m];
    dp[0] = grid[0][0];
    // Переход состояний: первая строка
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (int i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (int j = 1; j < m; j++) {
            dp[j] = Math.Min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}
min_path_sum.go
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
func minPathSumDPComp(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    // Инициализация таблицы dp
    dp := make([]int, m)
    // Переход состояний: первая строка
    dp[0] = grid[0][0]
    for j := 1; j < m; j++ {
        dp[j] = dp[j-1] + grid[0][j]
    }
    // Переход состояний: остальные строки и столбцы
    for i := 1; i < n; i++ {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0]
        // Переход состояний: остальные столбцы
        for j := 1; j < m; j++ {
            dp[j] = int(math.Min(float64(dp[j-1]), float64(dp[j]))) + grid[i][j]
        }
    }
    return dp[m-1]
}
min_path_sum.swift
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
func minPathSumDPComp(grid: [[Int]]) -> Int {
    let n = grid.count
    let m = grid[0].count
    // Инициализация таблицы dp
    var dp = Array(repeating: 0, count: m)
    // Переход состояний: первая строка
    dp[0] = grid[0][0]
    for j in 1 ..< m {
        dp[j] = dp[j - 1] + grid[0][j]
    }
    // Переход состояний: остальные строки
    for i in 1 ..< n {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0]
        // Переход состояний: остальные столбцы
        for j in 1 ..< m {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
        }
    }
    return dp[m - 1]
}
min_path_sum.js
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
function minPathSumDPComp(grid) {
    const n = grid.length,
        m = grid[0].length;
    // Инициализация таблицы dp
    const dp = new Array(m);
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for (let j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (let i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (let j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}
min_path_sum.ts
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
function minPathSumDPComp(grid: Array<Array<number>>): number {
    const n = grid.length,
        m = grid[0].length;
    // Инициализация таблицы dp
    const dp = new Array(m);
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for (let j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (let i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (let j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}
min_path_sum.dart
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
int minPathSumDPComp(List<List<int>> grid) {
  int n = grid.length, m = grid[0].length;
  // Инициализация таблицы dp
  List<int> dp = List.filled(m, 0);
  dp[0] = grid[0][0];
  for (int j = 1; j < m; j++) {
    dp[j] = dp[j - 1] + grid[0][j];
  }
  // Переход состояний: остальные строки
  for (int i = 1; i < n; i++) {
    // Переход состояний: первый столбец
    dp[0] = dp[0] + grid[i][0];
    // Переход состояний: остальные столбцы
    for (int j = 1; j < m; j++) {
      dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
    }
  }
  return dp[m - 1];
}
min_path_sum.rs
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
fn min_path_sum_dp_comp(grid: &Vec<Vec<i32>>) -> i32 {
    let (n, m) = (grid.len(), grid[0].len());
    // Инициализация таблицы dp
    let mut dp = vec![0; m];
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for j in 1..m {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for i in 1..n {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for j in 1..m {
            dp[j] = std::cmp::min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    dp[m - 1]
}
min_path_sum.c
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
int minPathSumDPComp(int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
    // Инициализация таблицы dp
    int *dp = calloc(m, sizeof(int));
    // Переход состояний: первая строка
    dp[0] = grid[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    // Переход состояний: остальные строки
    for (int i = 1; i < n; i++) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0];
        // Переход состояний: остальные столбцы
        for (int j = 1; j < m; j++) {
            dp[j] = myMin(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    int res = dp[m - 1];
    // Освободить память
    free(dp);
    return res;
}
min_path_sum.kt
/* Минимальная сумма пути: динамическое программирование с оптимизацией памяти */
fun minPathSumDPComp(grid: Array<IntArray>): Int {
    val n = grid.size
    val m = grid[0].size
    // Инициализация таблицы dp
    val dp = IntArray(m)
    // Переход состояний: первая строка
    dp[0] = grid[0][0]
    for (j in 1..<m) {
        dp[j] = dp[j - 1] + grid[0][j]
    }
    // Переход состояний: остальные строки
    for (i in 1..<n) {
        // Переход состояний: первый столбец
        dp[0] = dp[0] + grid[i][0]
        // Переход состояний: остальные столбцы
        for (j in 1..<m) {
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
        }
    }
    return dp[m - 1]
}
min_path_sum.rb
### Минимальная сумма пути: динамическое программирование с оптимизацией памяти ###
def min_path_sum_dp_comp(grid)
  n, m = grid.length, grid.first.length
  # Инициализация таблицы dp
  dp = Array.new(m, 0)
  # Переход состояний: первая строка
  dp[0] = grid[0][0]
  (1...m).each { |j| dp[j] = dp[j - 1] + grid[0][j] }
  # Переход состояний: остальные строки
  for i in 1...n
    # Переход состояний: первый столбец
    dp[0] = dp[0] + grid[i][0]
    # Переход состояний: остальные столбцы
    (1...m).each { |j| dp[j] = [dp[j - 1], dp[j]].min + grid[i][j] }
  end
  dp[m - 1]
end
Визуализация кода

Оставляйте свои идеи, вопросы и предложения в комментариях