[LeetCode] 64 Minimum Path Sum JavaScript

문제 링크

Minimum Path Sum - LeetCode

 

문제 유형

다이나믹 프로그래밍 (Dynamic Programming)

 

문제 풀이

해당 문제는 n x m 매트릭스를 나타내는 2차원 배열이 주어지고, (0,0)에서 (n, m)으로 가는 경로의 최소 합을 구하는 문제이다.

경로 이동은 현재 원소에서 오른쪽이나 아래로만 할 수 있다. 그러므로 각 원소의 이전 경로의 원소는 왼쪽에 있거나 위에 있다. 이는 왼쪽 원소까지의 최소 합과 위의 원소까지의 최소 합 중 더 작은 값에 현재 원소를 더하면 현재 원소까지의 최소 합이 된다. 그리고 이것은 모든 원소에게 성립하는 식이므로 다이나믹 프로그래밍 조건에 만족한다.

시간 복잡도는 O(nm)이고, 입력으로 주어지는 2차원 배열에 최소 합을 덮어씌우면 O(1)의 공간 복잡도로 문제 해결이 가능하다.

 

코드

var minPathSum = function(grid) {
    const n = grid.length; // row
    const m = grid[0].length; // col
    
    // grid 자체의 값을 덮어씌우면 O(1)의 공간복잡도로 문제를 해결할 수 있다.
    
    // 첫번째 열의 최소 합 계산
    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://www.youtube.com/watch?v=11oqpRgDF9Q