LeetCode 62 - Unique Paths (Medium)

문제

LeetCode - 62번

풀이 과정

전형적인 동적 계획법 을 활용한 경로 찾기 문제입니다.

시작 지점에서 이동할 수 있는 방향이 오른쪽과 아래쪽으로 고정되어 있기 때문에
dp(x, y) = (x, y) 지점에서 finish에 도달하는 경로의 개수 라고 정의한다면
다음과 같은 점화식을 세울 수 있습니다.

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

이때 격자를 벗어나거나 finish 지점에 도착하는 기저 사례를 처리해준다면 쉽게 문제를 해결할 수 있습니다.

코드

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const memo = new Array(m).fill(null).map((_) => new Array(n).fill(-1));

  function dp(x, y) {
    if (x === m - 1 && y === n - 1) {
      return 1;
    } else if (x < 0 || x >= m || y < 0 || y >= n) {
      return 0;
    }

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

    memo[x][y] = dp(x + 1, y) + dp(x, y + 1);
    return memo[x][y];
  }

  return (ret = dp(0, 0));
};