[LeetCode] 64. Minimum Path Sum

이전 문제들과 같이 풀이하되, 차이점은 각 셀마다의 가중치가 있다.

해당 가중치를 판단하여 셀에 값을 부여할 때 어떤 경로로 지나가는 것이 최소 값인지 판단할 수 있음

😎풀이

function minPathSum(grid: number[][]): number {
    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 j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 첫 번째 열 초기화
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // DP 테이블 채우기
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    // 오른쪽 아래 셀의 값이 최소 경로 합
    return dp[m-1][n-1];
}