(Leet Code JS)Minimum Path Sum

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

Minimum Path Sum - LeetCode

 

DP 알고리즘 이용.

주어진 grid의 크기는 m x n 이므로 각 변수에 length를 저장한다.

dp 테이블은 grid와 마찬가지로 m x n의 크기로 선언하여 0으로 초기화한다.

 

시작점인 [0, 0]에서 끝점 [m - 1, n - 1]로 향하기 때문에

dp[0][0]은 grid[0][0]으로 저장한다.

 

0번 행이 가장 맨 위이기 때문에 경로는 왼쪽에서 오른쪽으로 향하는 경로밖에 존재하지 않는다.

이를 처리하기 위해 0행 1열 ~ n - 1열까지 dp 테이블을 처리한다.

dp[0][i] = grid[0][i] + dp[0][i - 1]로 값을 갱신한다.

 

이후 1번 행부터 나머지 행과 열을 처리하면 된다.

이중 for문을 사용하여 DP 진행.

 

점화식

만약 j 열이 0이라면 위에서 오는 경로밖에 존재하지 않기 때문에

dp[i][j] = dp[i - 1][j] + grid[i][j]

로 처리한다.

 

만약 j가 0이 아닌 수라면 위 또는 왼쪽에서 오는 경로가 존재하므로

dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])

로 하여 위 또는 왼쪽에서 왔을 때 최소값을 dp 테이블에 저장한다.

 

리턴값은 끝점인 dp[m - 1][n - 1]다.

 

const minPathSum = (grid) => {
    const m = grid.length;
    const n = grid[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    
    dp[0][0] = grid[0][0];
    
    for(let i = 1; i < n; i++){
        dp[0][i] = grid[0][i] + dp[0][i - 1];
    }
    
    for(let i = 1; i < m; i++){
        for(let j = 0; j < n; j++){
            if(j === 0){
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else{
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
    }
    
    return dp[m - 1][n - 1];
};