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 down and right directions of movement are permitted. 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
if(m==1 || n==1) return 1;
else return countPaths(m-1, n) + countPaths(m, n-1);
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.
memo
pad matrix : int memo[][] = new int[m][n]
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 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 memo
. As you reach the last cell, it will eventually have the number of paths to the starting
cell.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];
}
}
public int countPaths(int m, int n){ }
C
Java
Python