[LeetCode] 64 _ minimumPathSum

나의 풀이

var minPathSum = function (grid) {
  let mLen = grid.length;
  let nLen = grid[0].length;

  const DP = [...new Array(mLen)].map(() => []);

  DP[0][0] = grid[0][0];

  for (let i = 0; i < mLen; i++) {
    for (let j = 0; j < nLen; j++) {
      if (i === 0 && j === 0) DP[i][j] = grid[i][j];
      // 우측 방향
      else if (j === 0) DP[i][j] = grid[i][j] + DP[i - 1][j];
      // 하단 방향
      else if (i === 0) DP[i][j] = grid[i][j] + DP[i][j - 1];
      // 대각선 방향
      else {
        DP[i][j] = grid[i][j] + Math.min(DP[i][j - 1], DP[i - 1][j]);
      }
    }
  }
  return DP[mLen - 1][nLen - 1];
};

 

1. DP 배열을 생성한 후

참고로 new Array(3).fill([]) 을 하면 DP[ [1] , [1] , [1] ] 이렇게 각 배열의 값이 복사되므로 위와 같이 생성해야 한다.

2. DP에 알맞은 값을 넣어주는데

 

 

우측 방향

하단 방향

그외 방향

경우에 따라 나눠서 DP[i][j]에 값을 채워넣는다.

 

 

 

 

 

해당 문제는 코드없는 알고리즘을 보고 추가적으로 학습했습니다.