.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
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.
Plain Text
복사
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Plain Text
복사
Constraints:
•
m == grid.length
•
n == grid[i].length
•
1 <= m, n <= 200
•
0 <= grid[i][j] <= 100
My solution
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
0 또는 양의 정수로 채워진 m x n 그리드가 주어진다. 좌측상단에서 우측하단으로 이동하는 경로를 찾는다. 그 경로에 속하는 모든 숫자들의 합이 최소가 되는
Note: You can only move either down or right at any point in time. 아래나 오른쪽 이동만 가능하다.
최단거리로 이동해야 하기 때문에 이동할 때마다 필요한 위치는 가장 가까운 왼쪽 칸과 가장 가까운 윗쪽 칸 중에 최솟값이다.
하지만 가장자리의 값을 구할 때는 가장 가까운 왼쪽 칸이나 가장 가까운 윗쪽 칸이 없는 경우가 있다. 이때는 최솟값을 구할 필요가 없다. 존재하는 값만 가지고 더해주면 된다.
그리고 첫번째 위치는 다른 위치에서 이동해온 것이 아니기 때문에 검사할 필요가 없다.
소스코드
/**
* @param {number[][]} grid
* @return {number}
*/
const minPathSum = function (grid) {
const M = grid.length;
const N = grid[0].length;
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (i !== 0 || j !== 0) {
if (i === 0) grid[i][j] += grid[i][j - 1];
else if (j === 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[M - 1][N - 1];
};
test('TC1', () => {
expect(
minPathSum([
[1, 3, 1],
[1, 5, 1],
[4, 2, 1],
])
).toStrictEqual(7);
});
test('TC2', () => {
expect(
minPathSum([
[1, 2, 3],
[4, 5, 6],
])
).toStrictEqual(12);
});
JavaScript
복사
