[LeetCode] 64. Minimum Path Sum

문제링크

https://leetcode.com/problems/minimum-path-sum/

제출 코드

/**
 * @param {number[][]} grid
 * @return {number}
 */
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    for (let i=0; i< grid.length; i++) {
       for (let j=0; j< grid[0].length; j++) {
            if (i==0 && j==0) { continue; }
            if (i == 0) {
                grid[i][j] = grid[i][j] + grid[i][j-1]
                continue;
            } 
            if (j == 0) {
                grid[i][j] = grid[i][j] + grid[i-1][j]
                continue;
            } 
            grid[i][j] = Math.min(grid[i][j] + grid[i][j-1], grid[i][j] + grid[i-1][j])
        }
    }
    return grid[grid.length-1][grid[0].length-1]
};

풀이 방법

점화식을 만들어 값을 비교하여 문제를 해결한다.
위쪽 grid[i][j] + grid[i][j-1]
아래쪽 grid[i][j] + grid[i-1][j]
위, 아래 값을 비교하여 더 작은 값으로 칸을 채워나간다.