This problem was asked by Facebook.

There is an N by M matrix of zeroes. Given N and M, write a function to count the number of ways of starting at the top-left corner and getting to the bottom-right corner. You can only move right or down.

For example, given a 2 by 2 matrix, you should return 2, since there are two ways to get to the bottom-right:

  • Right, then down
  • Down, then right

Given a 5 by 5 matrix, there are 70 ways to get to the bottom-right.

Idea behind the solution

Let s(n, m) be the number of paths for a matrix of size n, m. Knowing that s(2, 2) = 4, it can be shown that the solution for s(2, 2) = s(1, 2) + s(2, 1).

First, consider the matrix 2x2:

0   0
0   0

At the top-left corner we have only 2 options, first start going right or going down. If we choose start going right, the remaining possibilities would look like:

0
0

Therefore, we need to solve the number of paths for the matrix 2x1

On the other hand, if we had choosen to go down, the remaining possibilities would be as follows:

0   0

In other words, the matrix 1x2 is left.

Clearly, the number of paths for the matrix 2x1 and 1x2 to go to it's bottom-right is 1 and 1 respectively. Combining those 2 solutions, the possibilities for s(2, 2) = s(1, 2) + s(2, 1) = 2.

Applying the same logic for the matrix 3x2:

0   0   0
0   0   0

s(3, 2) = s(2, 2) + s(3, 1) = 2 + 1 = 3

For the matrix 3x3:

0   0   0
0   0   0
0   0   0

s(3, 3) = s(3, 2) + s(2, 3) = 5 + 5 = 10.

Note that, by remembering small solutions we can quickly calculate the number of paths for the current matrix. This is an instance of Dynamic Programming. By using a table s[i][j] that gives the solution for the matrix ixj, we can fill this table starting from s[1][1] until we get to the desidered size.

Please check the main.js snippet for the solution.

This solution originally posted at: Github by @Murillo2380