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 until we get to the desidered size.

Please check the main.js snippet for the solution.

This solution originally posted at: Github by @Murillo2380