64. Minimum Path Sum

💡풀이

var minPathSum = function (grid) {
  let rowLength = grid.length;
  let colLength = grid[0].length;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (i === 0 && j !== 0) grid[i][j] += grid[i][j - 1];
      if (i !== 0 && j === 0) grid[i][j] += grid[i - 1][j];
      if (i !== 0 && j !== 0) {
        grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
      }
    }
  }
  return grid[rowLength - 1][colLength - 1];
};

📝정리

오늘도 스스로는 못 풀었다.
DP와 관련된 문제다. 이런식으로 path의 최소값을 찾는 문제다.

// 맨 처음 grid의 형태다.
let grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1],
];

// 위의 풀이를 보면 총 3개의 if문이 있는데, 두번째 if문까지 실행된 결과가
// 다음과 같다.
grid = [
  [1, 4, 5],
  [2, 0, 0],
  [6, 0, 0],
];

// 그럼 나머지 부분들도 구해줘야 하는데, 결과는 다음과 같다.
grid = [
  [1, 4, 5],
  [2, 7, 6],
  [6, 8, 7],
];

// 위쪽 숫자와 왼쪽 숫자를 비교해 더 작은 숫자를 현재 자신과 더해주면 된다.
// 그럼 마지막 grid[3][3] 위치에 있는 숫자는 7이 된다. 이게 최소값이 된다.

좋은 스터디원 분들을 만나서 그 분들의 풀이와 설명을 아무런 대가 없이 받는 느낌이라 항상 감사합니다!

수정, 지적을 환영합니다.

문제 링크

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

LeetCode GitHub

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/submissions/