Different Paths#

A robot is located at the top-left corner of an m x n grid (the starting point is marked as Start in the figure below).
The robot can only move either down or to the right at a time, and is trying to reach the bottom-right corner of the grid (marked as Finish in the figure below).

For example, the figure above is a 7 x 3 grid. How many possible paths are there?

Example#

Solution#

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const table = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i=0; i<m; ++i){
        for(let k=0; k<n; ++k){
            if(i === 0 || k === 0) table[i][k] = 1;
            else table[i][k] = table[i-1][k] + table[i][k-1];
        }
    }
    return table[m-1][n-1];
};

Idea#

It's a relatively simple dynamic programming problem. Based on the requirements of the problem, a grid can be drawn directly. It's important to note that the robot can only move down or to the right at a time. For the example of a 7 x 3 grid provided in the problem, the following grid can be drawn.

By filling in the data according to the above table, we can easily find the pattern. The final value at the endpoint is simply the sum of the values of its upper and left nodes. In other words, it can be solved using a two-dimensional array and the dynamic programming equation dp[i][j] = dp[i-1][j] + dp[i][j-1]. Finally, return the value of the last element in this array. First, initialize the array by generating a m * n array using a constructor and filling it with 0. The reason for filling the outer array with 0 is that map will skip empty array slots. You can fill the outer array with any value, because the return value of the map callback function will override it. Then define a loop. If a certain index is 0 in the loop, then fill it with 1, otherwise add the value of the upper node and the left node to that point. This constructs the aforementioned table, and finally return the value of the last element in the table.

Daily Question#

References#