62. Unique Paths

💡풀이

// DP
const uniquePaths = (m, n) => {
  let currentRow = [];

  for (let i = 0; i < n; i++) {
    currentRow[i] = 1;
  }

  for (let row = 1; row < m; row++) {
    for (let j = 1; j < n; j++) {
      currentRow[j] = currentRow[j] + currentRow[j - 1];
    }
  }
  return currentRow[n - 1];
};

let m = 3,
  n = 7;

uniquePaths(m, n);

let grid = [
  [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0],
];

let gridNew = [
  [8, 4, 8, 7],
  [7, 4, 7, 7],
  [9, 4, 8, 7],
  [3, 3, 3, 3],
];

maxIncreaseKeepingSkyline(grid);

📝정리

• start에서 finish까지 갈 수 있는 모든 경우의 수를 구해야 한다. 문제 파악이 느려서 스스로 못 풀었다.

• DP 관련한 명확한 설명은 이 링크를 참조하자. 대략적인 규칙은 다음과 같다.

• 위 그림에서 볼 수 있다시피 아래의 요소와 좌측의 요소를 합하면 자신의 값이 된다.

• grid가 나오는 DP 문제는 대부분 비슷하다는 생각이 들었다. 비슷한 문제를 더 풀어봐서 감을 잡아야 할 듯.

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

문제 링크

https://leetcode.com/problems/unique-paths/

LeetCode GitHub

https://github.com/tTab1204/LeetCode