You're given a game board that has m x n squares on it, represented by an m x n array. Write a method - **down** and **right** directions of movement are permitted.

**Note: **

Your method should output the result in a reasonable amount of time for large values of m and n. If you're thinking of using DFS, consider the tree depth and branching factor for

`countPaths`

that takes in `m`

and `n`

and returns the number of possible paths from the top left corner to the bottom right corner. Only Your method should output the result in a reasonable amount of time for large values of m and n. If you're thinking of using DFS, consider the tree depth and branching factor for

`m`

and `n`

> 15!`m`

= number of rows, `n`

= number of columnsExample:

countPaths(m = 2, n = 2) => 2

as on the following 2x2 Board, the two paths are A->C->D and A->B->D

A B

C D

Need a **hand?** Try out these hints, one at a time.

This problem may appear trivial at first. In fact, it has a one line recursive solution of this form :

This will, however, result in an exponential time complexity and will most probably timeout for large values of

if(m==1 || n==1) return 1;

else return countPaths(m-1, n) + countPaths(m, n-1);

This will, however, result in an exponential time complexity and will most probably timeout for large values of

`m`

and `n`

. If you consider the recursion tree for the above solution, you'll notice many overlapping problems. There are many recursive branches branching off each board cell, with inevitable overlap between the branches of nearby cells. Since the direction of movement is heavily restricted, consider using Dynamic Programming with a `memo`

matrix that stores the number of solutions for each cell as you move across the board.
1) Create a 2D m x n

2) Fill the first row and column of**starting** cell, all cells in the first row have exactly 1 path (straight left) and all cells in the first column have exactly one path as well (straight up). So the strategy here is to build on this knowledge as you move across and down

3) Traverse

4) The last cell of the game board holds the answer to the problem.

`memo`

pad matrix : `int memo[][] = new int[m][n]`

2) Fill the first row and column of

`memo`

with `1`

s. This is because the direction of movement is limited to down and right when moving from start to finish. If you reverse the direction of movement and think about the number of paths from a cell to the `memo`

. As you reach the last cell, it will eventually have the number of paths to the `starting`

cell.3) Traverse

`memo`

in a loop starting from `memo[1][1]`

, while filling in each cell using the information from cells directly above and to the left of the current cell. To see why this works - consider `memo[0][0]`

, which is originally `1`

. Now, if you're at `memo[1][1]`

, you can either move up a row and then follow the path left or move left a column and follow the path above. Therefore, you must sum `memo[0][1]`

and `memo[1][0]`

to get the total number of paths possible :

for (int i = 1; i < m; i++){

for (int j = 1; j < n; j++){

memo[i][j] = memo[i-1][j] + memo[i][j-1];

}

}

4) The last cell of the game board holds the answer to the problem.

public int countPaths(int m, int n){ }

**C**

**Java**

**Python**