LeetCode 63 - Unique Paths II (Medium)

문제

LeetCode - 63번

풀이 과정

시작 지점에서 목표 지점에 도달할 수 있는 경우의 수를 찾는 문제입니다.
dp(x, y) 를 (x, y) 에서 오른쪽 하단 모서리에 도달하는 경우의 수라고 한다면 다음과 같은 점화식을 정의할 수 있습니다.

dp(x, y) = dp(x + 1, y) + dp(x, y + 1)

이때 dp(x, y) 에는 장애물이 없어야 하며 격자를 벗어나면 안됩니다.

코드

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  const memo = Array.from(Array(m), () => Array(n).fill(-1));

  function checkValidation(position) {
    if (
      position[0] < 0 ||
      position[0] >= m ||
      position[1] < 0 ||
      position[1] >= n
    )
      return false;
    return obstacleGrid[position[0]][position[1]] === 0;
  }

  function getPath(x, y) {
    if (x == m - 1 && y == n - 1) {
      return 1;
    }

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

    memo[x][y] = 0;

    const candidates = [
      [x, y + 1],
      [x + 1, y],
    ];
    for (const position of candidates) {
      if (checkValidation(position)) {
        memo[x][y] += getPath(position[0], position[1]);
      }
    }

    return memo[x][y];
  }

  if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) return 0;

  const answer = getPath(0, 0);

  return answer;
};