[LeetCode] 62. Unique Paths

https://leetcode.com/

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:

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

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

 

Code :

var uniquePaths = function(m, n) {
    // 초기값으로 m x n의 2차원 배열 생성
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

    // 첫 번째 행과 첫 번째 열의 값은 모두 1로 초기화
    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];
};

 

Solutions Code :

// Solution 1
var uniquePaths = function(m, n) {
    // 2D DP 배열을 0으로 초기화
    let dp = new Array(m).fill().map(() => new Array(n).fill(0));
    
    // 우측 열과 하단 행을 1로 초기화
    for (let i = 0; i < m; i++) {
        dp[i][n-1] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[m-1][j] = 1;
    }
    
    // DP 배열을 bottom-up 방식으로 채우기
    for (let i = m - 2; i >= 0; i--) {
        for (let j = n - 2; j >= 0; j--) {
            dp[i][j] = dp[i+1][j] + dp[i][j+1];
        }
    }
    
    // 결과는 좌상단에 저장된 값
    return dp[0][0];
};

// Solution 2
var uniquePaths = function(m, n) {
    // 계산된 결과를 저장하는 메모이제이션 테이블 생성
    let memo = new Array(m).fill(null).map(() => new Array(n).fill(-1));
    
    // 재귀 함수 호출을 통해 고유한 경로 수 계산 후 반환
    return uniquePathsRecursive(0, 0, m, n, memo);
};
var uniquePathsRecursive = function(x, y, m, n, memo) {
    // 목적지에 도달한 경우 (우하단 모서리), 1을 반환
    if (x === m - 1 && y === n - 1) {
        return 1;
    }
    
    // 이미 이 셀에 대한 결과를 계산했다면 메모 테이블에서 반환
    if (memo[x][y] !== -1) {
        return memo[x][y];
    }
    
    // 오른쪽과 아래로 이동하여 고유한 경로 수 계산
    let rightPaths = 0;
    let downPaths = 0;
    
    // 오른쪽으로 이동할 수 있는지 확인
    if (x < m - 1) {
        rightPaths = uniquePathsRecursive(x + 1, y, m, n, memo);
    }
    
    // 아래로 이동할 수 있는지 확인
    if (y < n - 1) {
        downPaths = uniquePathsRecursive(x, y + 1, m, n, memo);
    }
    
    // 계산 결과를 메모 테이블에 저장하고 반환
    memo[x][y] = rightPaths + downPaths;
    return memo[x][y];
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode