64. Сумма минимального пути (Minimum Path Sum)

Задание.

Дана сетка размером m x n, заполненная неотрицательными числами.

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

Примечание: В любой момент времени вы можете перемещаться только вниз или вправо.

Пример 1.

Входные данные: grid = [ [1,3,1], [1,5,1], [4,2,1] ]

Результат: 7

Пояснение: Потому что по пути 1 → 3 → 1 → 1 → 1 сумма минимальная.

Пример 2.

Входные данные: grid = [[1,2,3],[4,5,6]]

Результат: 12

Решение.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m,-1));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else {
                    int up = INT_MAX, left = INT_MAX;
                    if(i > 0) {
                        up = dp[i-1][j];
                    }
                    if(j > 0) {
                        left = dp[i][j-1];
                    }
                    dp[i][j] = grid[i][j] + min(up, left);
                }
            }
        }
        return dp[n-1][m-1];
    }
};

Способ решения.

Используется метод динамического программирования. Используется матрица dp, в ячейках которой хранится минимальная сумма пути (при движении из верхнего левого угла в нижний правый).

Минимальная сумма определяется, как сумма исходной ячейки и минимум из двух сумм:

• суммы пути слева

• суммы пути сверху

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

Результирующая минимальная сумма будет находится в правой нижней ячейке (dp[n-1][m-1]).