**Objective: **Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down.

**Approach:**

Recursion- Earlier we have seen “Print All Paths from Top left to bottom right in Two Dimensional Array“. Current problem is the subset of that problem. Here we will just count the number of paths, will not print them.

From every cell you will have two options to make a move, either to go right OR down. Base case will be check if you have reached to either last row OR last column then there is only one way to reach the last cell is to travel through that row or column. x

**Recursive Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public int count(int [][] arrA, int row, int col){ | |

//base case | |

//check if last row OR column is reached since after that only one path | |

//is possible to reach to the bottom right corner. | |

if(row==arrA.length–1 || col==arrA.length–1){ | |

return 1; | |

} | |

return count(arrA, row+1, col) + count(arrA, row, col+1); | |

} |

Time Complexity: It will be exponential since we are solving many sub problems repeatedly. We will use the Bottom-up approach of Dynamic programming and store the results of sub problems to reuse them in future.

**Dynamic Programming Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class NoOfPaths { | |

public int count(int [][] arrA, int row, int col){ | |

//base case | |

//check if last row OR column is reached since after that only one path | |

//is possible to reach to the bottom right corner. | |

if(row==arrA.length–1 || col==arrA.length–1){ | |

return 1; | |

} | |

return count(arrA, row+1, col) + count(arrA, row, col+1); | |

} | |

public int countDP(int [][] arrA){ | |

int result [][] = new int[arrA.length][arrA.length]; | |

//base case: if we have one cell then there is only one way | |

result[0][0] = 1; | |

//no of paths to reach in any cell in first row = 1 | |

for (int i = 0; i <result.length ; i++) { | |

result[0][i] = 1; | |

} | |

//no of paths to reach in any cell in first col = 1 | |

for (int i = 0; i <result.length ; i++) { | |

result[i][0] = 1; | |

} | |

for (int i = 1; i <result.length ; i++) { | |

for (int j = 1; j <result.length ; j++) { | |

result[i][j] = result[i–1][j] + result[i][j–1]; | |

} | |

} | |

return result[arrA.length–1][arrA.length–1]; | |

} | |

public static void main(String[] args) { | |

int arrA [][] = {{1,1,1},{1,1,1},{1,1,1}}; | |

NoOfPaths noOfPaths = new NoOfPaths(); | |

System.out.println("No Of Path (Recursion):- " +noOfPaths.count(arrA,0,0)); | |

System.out.println("No Of Path (DP):- " +noOfPaths.countDP(arrA)); | |

} | |

} |

**Output:**

No Of Path (Recursion):- 6 No Of Path (DP):- 6