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