[리트코드] 64. Minimum Path Sum - js

1. 문제

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

Minimum Path Sum - LeetCode

2. 코드

처음 푼 코드) 타임아웃

나의 풀이는 타임아웃이 떴다. 정답을 보니 재귀로 모든 길을 직접 돌아가며 최소값을 찾을 필요는 없었다. 역시 더 좋은 풀이가 있을 것 같았어 ㅠㅠ

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let answer = 100000000000000000;

    const move = (x,y,way) => {
        if(y === grid[0].length -1 && x === grid.length -1 && answer > way){
            answer = way;
        }
        else{
            if(x < grid.length - 1)
                move(x+1, y, way+grid[x+1][y]);
            if(y < grid[0].length - 1)
                move(x, y+1, way+grid[x][y+1]);
        }
    }

    move(0,0,grid[0][0]);

    return answer;
};

정답)

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const n = grid.length;
    const m = grid[0].length;
    
    // 각 요소는 그 요소의 왼쪽과 위쪽에 있는 요소에 영향을 받는다(오른쪽 및 아래 밖에 이동할 수 없기에).
    
    // 첫번째 열에 대한 계산
    // 첫번째 열에 있는 요소들은 왼쪽 요소가 없다. 그러므로 나의 위에 있는 요소들에만 영향을 받는다.
    for(let i=1; i<n; i++) {
        grid[i][0] += grid[i-1][0];
    }
    
    // 첫번째 행에 대한 계산
    // 첫번째 행은 위쪽 요소가 없다.
    for(let j=1; j<m; j++) {
        grid[0][j] += grid[0][j-1];
    }
    
    // 첫번째 행, 열에 대한 계산이 끝났으니
    // 현재 요소의 위쪽 또는 왼쪽 중 최소값을 저장하면 된다.
    for(let i=1; i<n; i++) {
        for(let j=1; j<m; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    
    return grid[n-1][m-1];
};

 

참고한 풀이)

https://leetcode.com/problems/minimum-path-sum/discuss/502072/javascript-95-speed-o-mn-time-o-1-space-w-comments/