Tags: JavaScript, Algorithms, Dynamic Programming, Matrix, Permutations and Combinations

Imagine a robot, standing at the top-left corner of a grid (marked as “Start” in the following diagram). The robot can only move down or to the right. Its mission? To reach the bottom-right corner of the grid (marked as “Finish”). The question is, how many different paths can the robot take to reach its destination?

+-----+------+------+------+------+------+------+------+------+------+------+
|Start|      |      |      |      |      |      |      |      |      |      |
+-----+------+------+------+------+------+------+------+------+------+------+
|     |      |      |      |      |      |      |      |      |      |      |
+-----+------+------+------+------+------+------+------+------+------+------+
|     |      |      |      |      |      |      |      |      |      |      |
+-----+------+------+------+------+------+------+------+------+------+------+
|     |      |      |      |      |      |      |      |      |      |      |
+-----+------+------+------+------+------+------+------+------+------+------+
|     |      |      |      |      |      |      |      |      |      |Finish|
+-----+------+------+------+------+------+------+------+------+------+------+

Since the robot can only move down or to the right, there are only two ways to reach any given cell: from the cell above it, or from the cell to its left. Therefore, the number of paths to a cell is the sum of the paths to the cell above it and the cell to its left.

In terms of dynamic programming, we can represent this as dp[i][j] = dp[i-1][j] + dp[i][j-1], where dp[i][j] is the number of paths to the cell in the ith row and jth column.

The initial state of the matrix is such that each cell in the first row and first column has only one path to it. So, if i===0 || j===0, then p[i][j]=1.

Here’s how we can implement this in JavaScript:

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const pd=[];
    for(let i=0;i<m;i++){
        pd[i]=[];
        for(let j=0;j<n;j++){
            if(i===0||j===0)pd[i][j]=1
            else pd[i][j]=pd[i-1][j]+pd[i][j-1]
        }
    }
    return pd[m-1][n-1]
};

But what if we looked at this problem from a different perspective, say, through the eyes of a primary school student studying combinatorics?

For any given cell, the number of steps down and to the right to reach that cell is fixed. For example, to reach the cell in the 4th row and 5th column, the robot must move down 3 steps and to the right 4 steps. However, the order in which these steps are taken can vary.

So, to reach the cell in the 4th row and 5th column, the robot must take a total of 3 + 4 = 7 steps. The number of paths to this cell is the number of ways to choose 3 of these 7 steps to move down, or equivalently, to choose 4 of these 7 steps to move right. This is given by the combination formula $C_7^3 =C_7^4=\frac{7\times6\times5}{3\times2\times1} = 35 $

For the general case, the number of paths to the cell in the m-1th row and n-1th column is $C_{m-1+n-1}^{m-1} = C_{m-1+n-1}^{n-1}$.

Here’s the JavaScript implementation for this approach:

function factorial(a,b){
    if(b===a)return a
    return a*factorial(a-1,b)
}

function combination(n, r) {
    if(r===0)return 1;
    return factorial(n,n-r+1) / factorial(r, 1);
}

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    return combination(m-1+n-1,m-1)
};

So, whether you’re a robot, a programmer, or a primary school student, there’s more than one way to navigate a grid!