The problem is to count all the possible paths from top left to bottom right of an m x n
matrix with the constraints that from each cell you can either move only to right or down. The cell is represented by Zeros and Ones, 0 means that there is path possible and 1 means it is an obstacle and there is no path possible through it.
We will explore two approaches:
 Brute force which takes O(N^N) time complexity
 Efficient Dynamic Programming approach O(N * M) time complexity
 A graph based approach in O(N * M) time complexity
Brute force 【O(N^N)】
Once approach is to generate all paths and then, determine which paths are valid.
The keys involved are:
 path length will be M + N
 There are M * N vertices/ cells
 The number of paths will be in the order of O((M * N)^(M+N)) that is O(N^N) if M=N
 There will be a few valid paths which we can determine by checking:
 if two cells in the path are adjacent or connected
 if the cells are available (0)
This will take exponential time O(N^N)
Dynamic Programming 【O(M * N)】
We will have to look for the subproblems to apply the dynamic programming approach. Can this problem be divided into subproblems so that each of those problems can be solved easily? The answer is, yes. You can find the value of number of paths to reach a particular cell by using the number of paths to reach the upper and left cell.

Optimal Substructure
 there are two possibilities for every cell X, either X is a valid path or it's a obstacle. If X is a valid path, then the value of total paths to reach X is the sum of total paths to reach the upper and left cell. If X is an obstacle, then the we can't reach that cell ever so the number of paths to reach that cell would be zero.
 let PATHS(X) indicate the number of paths to reach cell X.
PATHS(X) = PATHS(X.UP) + PATHS(X.LEFT) if X is zero
= 0 if X is one
here X.UP indicates upper cell of cell X and X.LEFT indicates cell to the left of X.
 Overlapping Subproblems
While solving the subproblems, we encounter that we have to find the solutions of the same subproblems again and again. When we have to calculate total number of paths to reach a particular cell, we would have to calculate the number of paths to reach to the cell left of it and the upper cell. We will need to calculate the number of paths to reach a cell multiple times i.e. when we are calculating the number of paths for the right cell and bottom cell of it. This is shows that overlapping subproblems exist.
Since Optimal Substructure and Overlapping Subproblems exist, we can use Dynamic Programming to derive an efficient solution.
Complexity
For a n x m
matrix,
 Time complexity:
Θ(mn)
 Space complexity:
Θ(mn)
Implementation
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int m = s.nextInt();
int mat[][] = new int[n][m];
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
mat[i][j] = s.nextInt();
int dp[][] = new int[n][m];
for(int i = 0;i<n;i++) {
if(mat[i][0] == 0)dp[i][0] = 1;
else break;
}
for(int i = 0;i<m;i++) {
if(mat[0][i] == 0) dp[0][i] = 1;
else break;
}
for(int i = 1;i<n;i++) {
for(int j = 1;j<m;j++) {
if(mat[i][j]!=1) dp[i][j]+=dp[i1][j]+dp[i][j1];
}
}
System.out.println(dp[n1][m1]);
}
}
Example
Consider the following matrix, 1 shows an obstacle.
Input:
3 3
0 1 0
0 0 0
1 0 0
Output:
2
For this input, the final dp array will be constructed as
index 0 1 2 0 1 0 0 1 1 1 1 2 0 1 2Graph based approach 【O(M * N)】
The idea is to:
 Create a graph with all cell as different vertices
 Edges in the graph will denote if movement between two cell is possible
 Once the graph is ready, each node will hold a 1D matrix such that:
 matrix[v1] which denotes number of paths from vertex v1 to the current vertex
 While traversal using DFS or BFS, moving from vertex v1 to v2 will be such that:
 matrix[S] of v2 is the product of matrix[S] of all directly connected vertices
 Finally, on reaching the destination vertex, the answer is matrix[S] where S is the source vertex
The actual complexity is O(E) where E is the number of edges
In a M * N matrix, there will be M * N edges at maximum and hence, the complexity is O(M * N).
On close inspection, you will see that:
 This graph based approach is same as the dynamic programming approach (for this problem)
 This approach can solve a wider problem with less restrictions on movement
Further reading
An extension to this problem is to allow moves in any of the four directions. We can't solve this using dynamic programming because current state depends not only on left and upper cells but also on right and bottom cells. This can be solved using:
 Dijkstra's Algorithm
 the graph approach we mentioned
This is a companion discussion topic for the original entry at http://iq.opengenus.org/countpathsfromtoplefttobottomrightofamatrix/