[LeetCode] DP, DFS - 62. Unique Paths

문제

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 * 109.

 

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

코드

DFS

const uniquePaths = (m, n) => {
    const memo = new Array(m).fill(0).map(() => new Array(n));
    
    const dfs = (row, col) => {
        if(row < 0 || col < 0 || row >= m || col >= n) {
            return 0;
        }

        if(row === m - 1 && col === n - 1) {
            return 1;
        }

        if(memo[row][col]) {
            return memo[row][col]
        }

        const res = dfs(row + 1, col) + dfs(row, col + 1);
        memo[row][col] = res;
        return res;
    }

    return dfs(0, 0)
}

DP

var uniquePaths = function(m, n) {
    let dp = new Array(m).fill(0).map(() => new Array(n));
    for (let row = m-1; row >= 0; row--) {
        for (let col = n-1; col >= 0; col--) {
            if (row === m-1 || col === n-1) {
                dp[row][col] = 1;
            } else {
                dp[row][col] = dp[row][col+1] + dp[row+1][col];
            }
        }
    }
    return dp[0][0];
    // T.C: O(M*N)
    // S.C: O(M*N)
};