Find total number of paths in a matrix of 0's and 1's I am working on a program which states that:

You are given a 2-D matrix with M rows and N columns.You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1’s and 0’s. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through that cell. Return the number of paths from top-left cell to bottom-right cell.(i.e. (0,0)to(M-1,N-1)). Since answer can be large thus you have to return ans%(10^9+7).

static int count(int a[][], int i, int j) {
    int rows = a.length;
    int cols = a[0].length;
    if(a[i][j] == 0)  return 0;
    if (i == rows - 1 &amp;&amp; j == cols - 1)
        return a[i][j];
    else if (i == rows - 1)
        return a[i][j + 1];
    else if (j == cols - 1)
        return a[i + 1][j];
    else if (a[i][j] == 1)
        return count(a, i + 1, j) + count(a, i, j + 1);
    else
        return 0;
}


How can we improve the performance of this program?
Recursion is not recommended.  First, you would likely end up repeating calculations for cells that are approached from multiple paths.  Second, the call stack would be as deep as the longest path, and you could easily crash with a StackOverflowError for a large maze.

Instead, I recommend using dynamic-programming, building a 2D table where each entry is the number of paths from the start to that location.  Every paths[r][c] is calculated exactly once, and in an order that is gentle to the cache.

public static int count(int[][] a) {
    int[][] paths = new int[a.length][a[0].length];
    if ((paths[0][0] = a[0][0]) == 0) {
        return 0;
    }
    for (int c = 1; c &lt; a[0].length; c++) {
        paths[0][c] = a[0][c] * paths[0][c - 1];
    }
    for (int r = 1; r &lt; a.length; r++) { 
        paths[r][0] = a[r][0] * paths[r - 1][0];
        for (int c = 1; c &lt; a[r].length; c++) {
            paths[r][c] = a[r][c] * (paths[r - 1][c] + paths[r][c - 1]);
        }
    }
    return paths[a.length - 1][a[0].length - 1];
}


You can even even build the paths one row at a time, while the maze a is being loaded. Furthermore, it is possible to modify the code to use less memory, since only the last two rows of paths are relevant at any given time. However, for simplicity, I haven't done that here: if you can afford to keep the entire a in memory, then you can probably also afford to keep another 2D array of the same size.