Сложность: 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)), с учётом граничных условий.
😎 Решение:
var minPathSum = function (grid) {
let dp = new Array(grid.length)
.fill()
.map(() => new Array(grid[0].length).fill(0));
for (let i = grid.length - 1; i >= 0; i--) {
for (let 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];
};Ставь 👍 и забирай 📚 Базу знаний