Сложность: 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][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];
}
}Ставь 👍 и забирай 📚 Базу знаний