[Leetcode] Unique Paths

62. Unique Paths

There is a robot on an m x ngrid. 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 mand 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

How to approach?

Dynamic Programming

function uniquePaths(m: number, n: number): number {
    if (m === 1 || n === 1) {
        return 1;
    }
    let dp = new Array(m).fill(0).map(() => new Array(n).fill(1))
    for (let row = 1; row < m; ++row) {
        for (let col = 1; col < n; ++col) {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
        }
    }
    return dp[m - 1][n - 1]
};

1. when m or n is 1, then return 1 since only one way direction is available.
2. create array filled with 1 as m*n shape. m rows and n columns.
3. create 2 for loop which takes row and column starting from 1.
4. each inner cells is sum of the above cell and left cell's calculated paths.
5. and lastly return the last cell at the bottom right corner.
6. think of the firs row and first column filled with 1 because it only goes 1 way. since the robot move to the right or to the down side.

summary

think of this as structured table filled with 1 for the first time and fill the inner cells by summing up based on the already calculated results in the table.