LeetCode 64 - Minimum Path Sum (Medium)

문제

LeetCode - 64번

풀이 과정

이동 방향이 고정되어 있는 상태에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다.
각 칸을 하나의 정점으로 생각하면 이동 방향이 오른쪽 혹은 아래로 고정되어 있으므로 이를 그래프로 모델링하여
다익스트라 알고리즘이나 플로이드와 같은 최단 경로 알고리즘을 사용할 수도 있을 것 같습니다.
하지만 그보다 간단하게 동적 계획법 을 활용하여 문제를 해결할 수 있습니다.

만약 dp(x, y) = (x, y)에서 출발해서 (m, n)에 도달 할 수 있는 최단경로 라고 정의한다면
다음과 같은 점화식을 세울 수 있습니다.

dp(x, y) = min(dp(x+1, y), dp(x, y+1)) + cost(x, y), 이때 cost는 현재 (x, y) 에서 필요한 비용

평소 Javascript로 Node.js나 Vue.js 개발할 때 일차원 배열을 주로 사용하였는데

이번 문제를 통해서 Javascript 에서 다차원 배열을 생성하고 초기화하는 방법을 익힐 수 있었습니다.

코드

/**

* @param {number[][]} grid

* @return {number}

*/

var minPathSum = function (grid) {

const M = grid.length;

const N = grid[0].length;

const memo = new Array(M).fill(0).map((_) => new Array(N).fill(-1));



const INF = Number.MAX_SAFE_INTEGER;



const dp = function (x, y) {

// 범위를 벗아난다면

if (x < 0 || x >= M || y < 0 || y >= N) {

return INF;

}

// 목표 지점에 도달한다면

else if (x === M - 1 && y === N - 1) {

return grid[x][y];

}



if (memo[x][y] !== -1) {

return memo[x][y];

}



memo[x][y] = Math.min(dp(x + 1, y), dp(x, y + 1)) + grid[x][y];

return memo[x][y];

};



const a = dp(0, 0);

return a;

};



const grid = [

[1, 3, 1],

[1, 5, 1],

[4, 2, 1],

];



console.log(minPathSum(grid));

Javascript 다차원 배열 생성 참고자료

• https://smilerici.tistory.com/71