Сложность: 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)), с учётом граничных условий.
😎 Решение:
func minPathSum(_ grid: [[Int]]) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: grid[0].count), count: grid.count)
for i in stride(from: grid.count - 1, through: 0, by: -1) {
for j in stride(from: grid[0].count - 1, through: 0, by: -1) {
if i == grid.count - 1 && j != grid[0].count - 1 {
dp[i][j] = grid[i][j] + dp[i][j + 1]
} else if j == grid[0].count - 1 && i != grid.count - 1 {
dp[i][j] = grid[i][j] + dp[i + 1][j]
} else if j != grid[0].count - 1 && i != grid.count - 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]
}Ставь 👍 и забирай 📚 Базу знаний