[LeetCode] Unique Paths

https://leetcode.com/problems/unique-paths/description/?envType=study-plan-v2&envId=leetcode-75

 

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]).

The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n -1]).

The robot can only move either down or right at any point in time.

Given the two integers m and n, 

return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
 
Constraints:
1 <= m, n <= 100

---

어릴 때 이런 문제 많이 풀었던 것 같은데ㅋㅋㅋ

확률과 통계인가.. 경우의 수 같은거 구할 때 많이들 했던 것 같다.

 

로봇이 세로 m칸, 가로 n칸의 그리드 판의 좌상단에서 우하단으로 이동하는 고유한 경우의 수를 구하는 문제다.

로봇은 반드시 오른쪽 또는 아래칸으로만 이동할 수 있다.

따라서 로봇은 무조건 가로로는 n-1칸만 이동가능하며, 세로로는 m-1칸만 이동가능하다.

그러니까.. 결국 (n-1) + (m-1) 개의 빈 칸 중에서 n-1칸 또는 m-1칸 채우는 방법을 구하면 된다.

 

 

그건 조합으로 구할 수 있음.

즉, C(n+m-2, n-1)을 구하면 된다.

 

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const factorial = (n) => {
    let res = 1;
    for(let i=1; i<=n; i++){
        res *= i;
    }
    return res;
}
var uniquePaths = function(m, n) {
    return factorial(n+m-2) / (factorial(n-1)*factorial(m-1));
};

 

이렇게 짰더니 

TypeError: 86493224.99999999 is not valid value for the expected return type integer

어느 정도 큰 숫자가 들어갈 때 이런 에러메시지가 떴다.

 

계산되는 값이 커져서 Number.MAX_SAFE_INTEGER를 초과하면 부동소수점 오차로 정수를 리턴하지 않아 생긴 이슈다.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER

Number.MAX_SAFE_INTEGER - JavaScript | MDN

이럴 때는 BigInt를 써 줘야 한다...

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt

BigInt - JavaScript | MDN

 

const factorial = (n) => {
    let res = 1n;
    for(let i=1n; i<=BigInt(n); i++){
        res *= i;
    }
    return res;
}
var uniquePaths = function(m, n) {
    const top = factorial(n+m-2);
    const bottom = factorial(n-1) * factorial(m-1);
    const result = top / bottom;
    return Number(result);
};

 

또 리턴할 때는 Number로 해 줘야 해서 또 캐스팅해서 리턴해준다.

 

근데 이건 다차원 DP문제인데 DP로 풀지 않았군요.

예의상 DP로 풀어낸 0ms짜리 답변도 가져와 본다.

var uniquePaths = function (m, n) {
    const dp = Array(m)
        .fill()
        .map(() => Array(n).fill(0));

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

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};

 

첫 행과 첫 열을 모두 1로 채우고, 나머지는 0으로 채운다. 최종 결과는 우하단에 위치한다.

dp[i][j]는 (i,j) 위치까지 올 수 있는 경로의 수이다.

(i, j) 위치까지 가는 방법은 (i-1, j)에서 한 칸 아래로 가거나, (i, j-1)에서 한 칸 오른쪽으로 갈 수 있다.

그 값을 dp[i][j] = dp[i-1][j] + dp[i][j-1] 를 통해 누적 계산하는 방식이다.

 

 

고차원 점화식은 이런 식으로 쓸 수 있군..