LeetCode Minimum Path Sum (JavaScript)

링크 : https://leetcode.com/problems/minimum-path-sum/description/

문제 설명

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.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

---

문제 풀이

DP를 이용하여 풀이

핵심 :  각 자리에서 도달할 수 있는 최단 거리를 저장해 나가면서 계산

1. 첫 번째 row는 이전 row의 값을 더해주면 됨, 첫 번째 col은 이전 col의 값을 더해주면 됨.

2. 오른쪽, 아래로 이동이 가능하므로 위, 왼쪽에서 올 수 있는 최단거리의 값을 자리에 더해줌.

3. 최종적으로 m - 1, n - 1좌표는 최단 거리가 저장되어있음.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var 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) {
                if (j > 0) {
                    grid[i][j] += grid[i][j - 1];
                }
            } else if (j === 0) {
                if (i > 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];
};

---

결론

DP를 활용해 각 자리를 어떠한 방식으로 관리를 할 것인가가 중요