Сложность: medium
На сетке m x n, заполненной неотрицательными числами, найдите путь от (0, 0) до (m - 1, n - 1) с минимальной суммой.
Можно двигаться только вправо или вниз.
Пример:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7
👨💻 Алгоритм:
1⃣Инициализировать матрицу dp такого же размера, где dp[i][j] будет хранить минимальную сумму пути до конца из позиции (i, j)
2⃣Заполнить dp в обратном порядке, начиная с правого нижнего угла.
Для каждой ячейки:
dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1]) — если оба пути доступны
Учитывать границы (последняя строка и столбец) отдельно
3⃣Вернуть dp[0][0] — минимальную сумму пути из начала в конец
😎 Решение:
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, 0));
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 && j != n - 1)
dp[i][j] = grid[i][j] + dp[i][j + 1];
else if (j == n - 1 && i != m - 1)
dp[i][j] = grid[i][j] + dp[i + 1][j];
else if (j != n - 1 && i != m - 1)
dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
else
dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
};Ставь 👍 и забирай 📚 Базу знаний