# Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objective: Count all the paths from left top corner to right bottom corner in two dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

Recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub problems which will be solved again and again to get the final solution. read this : “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Create two dimensional resultCount array to store the number of paths from top left corner.

Base Case: To reach to any cell in either first row or column from first cell(top left at 0,0) will be 1.

You can reach to any cell from 3 different ways, from left, from top, from diagonal. So total no of paths to reach to that cell will be sum of all the paths to reach to left, top and diagonal cell. see picture Example: Complete Code:

 public class CountAllPaths { int rowCount; int colCount; int[][] arrA; public CountAllPaths(int arrA[][]) { this.arrA = arrA; rowCount = arrA.length; colCount = arrA.length; } public int countAllResursion(int currentRow, int currentColumn) { if (currentRow == rowCount – 1) { return 1; } if (currentColumn == colCount – 1) { return 1; } return countAllResursion(currentRow + 1, currentColumn) + countAllResursion(currentRow, currentColumn + 1) + countAllResursion(currentRow + 1, currentColumn + 1); } public int printAllDynamic(int[][] arrA) { int[][] resultCount = new int[arrA.length][arrA.length]; for (int i = 0; i < arrA.length; i++) { resultCount[i] = 1; } for (int i = 0; i < arrA.length; i++) { resultCount[i] = 1; } for (int i = 1; i < arrA.length; i++) { for (int j = 1; j < arrA.length; j++) { resultCount[i][j] = resultCount[i][j – 1] + resultCount[i – 1][j] + resultCount[i – 1][j – 1]; } } return resultCount[arrA.length – 1][arrA.length – 1]; } public static void main(String args[]) { int[][] a = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; CountAllPaths p = new CountAllPaths(a); System.out.println("No of Paths By Recursion: " + p.countAllResursion(0, 0)); System.out.println("No of paths By Dynamic Programming: " + p.printAllDynamic(a)); } }

view raw
CountAllPaths.java
hosted with ❤ by GitHub

Output:

```No of Paths By Recursion: 13
No of paths By Dynamic Programming: 13
```

### 1 thought on “Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths”

1. what is arrA.length? and what is arrA.length?