Постановка задачи
Дана сетка m x n, заполненная неотрицательными числами,
найдите путь из левого верхнего угла в правый нижний, который минимизирует сумму всех чисел на его пути.
Примечание: В любой момент времени вы можете двигаться только вниз или вправо.
Постановка задачи взята с сайта: https://leetcode.com/problems/minimum-path-sum
Пример 1:
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Пример 2:
Input: grid = [[1, 2, 3], [4, 5, 6]]
Output: 12
Ограничения:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
Объяснение
Подход грубой силы
Метод грубой силы заключается в генерации всех возможных путей от левого верхнего до правого нижнего. Мы вычисляем сумму всех этих путей и находим минимум. Решение работает для массивов небольшого размера, но для массивов большого размера произойдет сбой.
Оптимальная подструктура
Путь к (m, n) должен проходить через одну из двух ячеек: (m — 1, n) или (m, n — 1). Минимальная стоимость достижения (m, n) может быть рассчитана как «минимум из двух клеток плюс решетка(m, n)».
minimumCost(m, n) = min(minimumCost(m - 1, n), minimumCost(m, n - 1)) + grid(m, n)
int minCost(int grid[R][C], int m, int n)
{
if (n < 0 || m < 0)
return INT_MAX;
else if (m == 0 && n == 0)
return grid[m][n];
else
return grid[m][n] +
min(
minCost(grid, m - 1, n),
minCost(grid, m, n - 1)
);
}
Динамическое программирование
Приведенная выше оптимальная подструктура решается с помощью рекурсивного подхода. Но, если мы внимательно посмотрим, то при таком подходе одни и те же подпроблемы вычисляются снова и снова.
Мы можем избежать повторного вычисления одних и тех же подпроблем, используя подход динамического программирования. Мы создаем двумерный массив и решаем задачу снизу вверх.
Давайте перейдем к алгоритму, чтобы лучше понять его.
- set m = grid.size()
n = grid[0].size()
dp(m, vector<int>(n))
- loop for i = 0; i < m; i++
loop for j = 0; j <n; j++
if i == 0 && j == 0
- set dp[i][j] = grid[i][j]
else if i == 0
- set dp[i][j] = dp[i][j - 1] + grid[i][j]
else if j == 0
- set dp[i][j] = dp[i - 1][j] + grid[i][j]
else
- set dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
- for end
- return dp[m - 1][n - 1]
Временная сложность этого подхода составляет O(N^2), а пространственная — O(M*N).
Давайте проверим наш алгоритм на C++, Golang и Javascript.
Решение на C++
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) {
dp[i][j] = grid[i][j];
} else if(i == 0) {
dp[i][j] = dp[i][j - 1] + grid[i][j];
} else if(j == 0) {
dp[i][j] = dp[i - 1][j] + grid[i][j];
} else {
dp[i][j] = min(dp[i- 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1];
}
};
Решение на Golang
func minPathSum(grid [][]int) int {
m := len(grid)
n := len(grid[0])
dp := make([][]int, m)
for k := range dp {
dp[k] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j == 0 {
dp[i][j] = grid[i][j]
} else if i == 0 {
dp[i][j] = dp[i][j - 1] + grid[i][j]
} else if j == 0 {
dp[i][j] = dp[i - 1][j] + grid[i][j]
} else {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
}
return dp[m - 1][n - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Решение для Javascript
var minPathSum = function(grid) {
let m = grid.length;
let n = grid[0].length;
let dp = new Array(m);
for(let k = 0; k < dp.length; k++) {
dp[k] = new Array(n);
}
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(i == 0 && j == 0) {
dp[i][j] = grid[i][j];
} else if(i == 0) {
dp[i][j] = dp[i][j - 1] + grid[i][j];
} else if(j == 0) {
dp[i][j] = dp[i - 1][j] + grid[i][j];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1];
};
Давайте проверим наш алгоритм для примера 2.
Input: grid = [[1, 2, 3], [4, 5, 6]]
Step 1: m = grid.size()
= 2
n = grid[0].size()
= 3
dp(2, 3)
Step 2: loop for i = 0; i < m
0 < 2
true
loop for j = 0; j < n
0 < 3
true
if i == 0 && j == 0
true
dp[i][j] = grid[i][j]
= grid[0][0]
= 1
dp = [[1, 0, 0], [0, 0, 0]]
j++
j = 1
j < n
1 < 3
true
if i == 0 && j == 0
true
else if i == 0
true
dp[i][j] = dp[i][j - 1] + grid[i][j]
= dp[0][1 - 1] + grid[0][1]
= dp[0][0] + grid[0][1]
= 1 + 2
= 3
dp = [[1, 3, 0], [0, 0, 0]]
j++
j < n
2 < 3
true
if i == 0 && j == 0
true
else if i == 0
true
dp[i][j] = dp[i][j - 1] + grid[i][j]
= dp[0][2 - 1] + grid[0][1]
= dp[0][1] + grid[0][2]
= 3 + 3
= 6
dp = [[1, 3, 6], [0, 0, 0]]
j++
j < n
3 < 3
false
i++
i = 1
Step 3: loop for i < m
1 < 2
true
loop for j = 0; j < n
0 < 3
true
if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
true
dp[i][j] = dp[i - 1][j] + grid[i][j]
= dp[1 - 1][0] + grid[1][0]
= dp[0][0] + grid[1][0]
= 1 + 4
= 5
dp = [[1, 3, 6], [5, 0, 0]]
j++
j < n
1 < 3
true
if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
false
else
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
= min(dp[1][1 - 1], dp[1 - 1][1]) + grid[1][1]
= min(dp[1][0], dp[0][1]) + 5
= min(5, 3) + 5
= 3 + 5
= 8
dp = [[1, 3, 6], [5, 8, 0]]
j++
j < n
2 < 3
true
if i == 0 && j == 0
false
else if i == 0
false
else if j == 0
false
else
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
= min(dp[1][2 - 1], dp[1 - 1][2]) + grid[1][2]
= min(dp[1][1], dp[0][2]) + 6
= min(8, 6) + 6
= 6 + 6
= 12
dp = [[1, 3, 6], [5, 8, 12]]
j++
j < n
3 < 3
false
i++
i = 2
Step 4: loop for i < m
2 < 2
false
Step 5: return dp[m - 1][n - 1]
dp[2 - 1][3 - 1]
dp[1][2]
12
We return the answer as 12.