Count paths from Top Left to Bottom Right of a Matrix using Dynamic Programming【O(M*N)】

Reading time: 35 minutes

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.

1. 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.

2. 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[i-1][j]+dp[i][j-1];
			}
		}
		System.out.println(dp[n-1][m-1]);
	}

}

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

Graph 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