LeetCode - 64. Minimum Path Sum (JavaScript)

Medium, DP

RunTime : 53 ms / Memory : 51.70 MB

문제

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.

풀이

• 많이 접해본 유형의 DP문제
• 첫 행과 첫 열을 채워준 후 안 쪽을 dp로 탐색하면 쉽다.

var minPathSum = function(grid) {
    var n = grid.length;
    var m = grid[0].length;

    var dp = Array.from(Array(n), () => Array(m).fill(0))
    
    dp[0][0] = grid[0][0];

    for(let i = 1; i < n; i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    for(let j = 1; j < m; j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }


    for(let i = 1; i < n; i++){
        for(let j = 1; j < m; j++){
            dp[i][j] = Math.min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j]);
        }
    }

    return dp[n-1][m-1];
};