Counting paths on grid : dynamic programming

Counting paths on grid

Given a maze as shown in figure below, find count of all paths in maze to reach at right most bottom cell from leftmost top cell. You can move right, down and diagonally and not left.This problem is called as “Counting paths on grid”. We will solve this problem using recursion and dynamic programming both.

To understand basic principles of dynamic programming, please refer: Dynamic Programming basics

Best thing about Maze/Grid problems is that they reduce to smaller problem as soon as we make one move from current position. For example in this problem, after making one move, problem reduces as how many paths are possible from new cell to destination cell. Add 1 to solution of this subproblem and you have solution to original problem.

However, in counting paths on grid problem, we can move in three direction. Once we move in a particular direction (let’s say right) from a cell, that does not mean that all paths possible by going to other directions (down and diagonal) should not be counted. Hence, for each cell, count possible path if move is made to right, possible paths if move was made to down and possible paths move was made diagonally and add them up.

Counting paths on grid : Recursive approach

When solution to problem depends on solution to smaller problems, that usually hints towards recursion. As counting paths on grid problem reduces to smaller problem with each move, recursion is natural choice. For recursion to succeed, find is what is base case or terminating condition for the recursion condition? In counting paths on grid problem, base case will be when we reach destination cell (rightmost bottom cell). Let i and j be current row and column of the grid, base case would be

if(i == m && j == n) return 1

Recursion formulation for paths on grid problem would be

PossiblePaths(i,j,m,n) = PossiblePaths(i+1,j, m,n) // Move down
                         + PossiblePaths(i, j+1, m,n) // Move right
                         + PossiblePaths(i+1, j+1,m,n); // Move diagonally

Counting paths on grid : Recursive implementation

#include <stdio.h>
 
int PossiblePaths(int i,int j, int m, int n){
	if(i > m || j > n) return 0; 
 
	if(i == m && j == n) return 1;
 
	return PossiblePaths(i+1,j, m,n) 
			+ PossiblePaths(i, j+1, m,n) 
			+ PossiblePaths(i+1, j+1,m,n);
}
 
int main(void) {
 
	int m = 4;
	int n = 4;
	printf("\n Number of paths in maze : %d",PossiblePaths(0,0,m,n) );
	return 0;
}

Count paths on grid : dynamic programming

Let’s see what happens in execution of recursive implementation.  Size of maze is 3×3, m and n equal to 3. To start i and j equal to 0.
counting paths on grid

From execution tree of recursive execution, it is evident that there are subproblems which are calculated multiple times. Number of such subproblems increases as size of maze increases and tree gets bigger. We know that there are two basic conditions that a problem must satisfy before dynamic programming can be applied to it.

1. There should be optimal subproblem, which reduce original problem to smaller subproblem.
2. There should be overlapping subproblems which asks for tabulation of the results from subproblems, to be used for solution of bigger problems.

With counting paths in maze problem, both conditions to apply DP are met.
To store results of subproblems, create a two dimensional, Table with dimensions same as maze.Table[i][j] stores number of paths possible to reach Maze[i][j]. Answer will Table[m][n].

Table (i,j) can be reached at by either coming from Table(i-1,j) (Moving down) or by coming from Table(i,j-1) (Moving right) or by coming from Table (i-1, j-1) (Moving diagonally).

Table[i][j] is calculated as:

Table(i,j) = Table(i-1,j) + Table(i,j-1)+ Table(i-1,j-1)
Table[i][0] = Table[0][j] = 1

Counting paths on grid : dynamic programming implementation

#include<stdlib.h>
#include<stdio.h>
 
int PossiblePaths(int m,int n){
	int Table[m+1][n+1];
	int i,j;
 
	for(i=0;i<=m; i++){
		Table[i][0] =1;
	}
	for(i=0;i<=n; i++){
		Table[0][i] =1;
	}
	for(i=1; i<=m; i++ ){
	    for(j=1; j<=n; j++){
		Table[i][j] = Table[i-1][j] 
                              + Table[i][j-1] 
                              + Table[i-1][j-1];
	    }
	}
	return Table[m][n];
}
 
int main(){
   printf("%d",PossiblePaths(4,4));
   return 0;
}

Problem with above implementation is it uses m*n space. This can be optimized by storing only row at a time instead of entire table. Why? Because from the equation to calculate Table[i][j], we can see that it it only depends on previous row. Space optimized version (Thanks to Jakube for suggesting it )

#include<stdlib.h>
#include<stdio.h>
 
int PossiblePaths(int m,int n){
	int Table[n+1];
	int diagonalSum = 0;
 
	for(int i=0;i<=n; i++){
		Table[i] = 1;
	}
	for(int i=1; i<=m; i++ ){
		int diagonalSum = 1;
		for(int j=1; j<=n; j++){
			int temp = Table[j];
			Table[j] = Table[j] +  Table[j-1] +  diagonalSum;
			diagonalSum = temp;
		}
	}
	return Table[n];
}
 
int main(){
   printf("%d",PossiblePaths(4,4));
   return 0;
}

Finding all paths in a maze using dynamic programming takes extra O(n2)memory but reduces exponential time complexity to O(n2).

Please share if you find something wrong or missing. If you want to contribute to site, please refer Publish on Algorithms and Me and contact us. We would be happy to publish your work and in turn will pay you too.

  • Jakube

    You can easily improve this to O(N) memory, since for calculating the values of the next row, you only need the values of last row. Therefore you can overwrite the last row with the new values. You just have to be carefully, so you don’t overwrite the diagonally entry.

    • http://algorithmsandme.in/ Jitendra Sangar

      Hi,
      Thanks for comment. I have implemented as per the suggestion and updated post.

  • clyton dantis

    Your recursive routine does not terminate. You have not handled the case where i == m but j!=n .

    • http://algorithmsandme.in/ Jitendra Sangar

      We should not terminate when i==m and j!=n because we want to calculate number of possible paths to reach cell (m,n).

      • clyton dantis

        but I get a stack overflow error on running the code. the variable ‘ i ‘ keeps on increasing beyond the value of m

        • http://algorithmsandme.in/ Jitendra Sangar

          Got it. You should add checks for i<m and jm or j > n, we should return 0. Will change the code.
          Thanks for pointing out.

  • Pingback: Find Minimum Cost Path in a 2D Matrix: DP – Algorithms and Me()