Dynamic Programming -Grid Travel with Recursion And Memoization

Problem statement is : A robot is situated at top left corner of an m x n grid. It needs to travel to the bottom right corner. The robot can only move either right or down at any point

This is another classical dynamic programming problem.

As discussed in our previous fibonacci problem, for any dynamic programming you can first see if the problem can be visualized as a recursion tree.

Question: Calculate total number of ways user can travel from S(0,0) to E(2,2)

User needs to travel from S to E

At any node you can either move towards right or down.

By analyzing the grid, you can see different number of ways from S to E are

1. (0,0) → (0,1) → (0,2) →(1,2) →(2,2)
2. (0,0) → (0,1) → (1,1) → (2,1) →(2,2)
3. (0,0) → (1,0) → (1,1) → (1,2) →(2,2)
4. (0,0) → (1,0) → (2,0) → (2,1) → (2,2)
5. (0,0) → (1,0) → (1,1) → (2,1) →(2,2)
6. (0,0) → (0,1) → (1,1) → (1,2) →(2,2)

Recursion Tree

In this recursion tree

1. When the execution reaches position (2,2) , we know that current path is a valid path from Source to Destination. So we would need to return 1.
2. If the execution exceeds either number of rows or columns of the grid, we have to return 0 as it can not reach (2,2)

Time complexity And Space Complexity

• The height of the tree is m + n and its a binary tree. so the time complexity is O(2^(m+n))
• Space complexity is O(m+n)

Java Program for Recursive Solution

public class Solution {
   public static void main(String[] args) {
      int[][] input = {{3, 3}, {6, 5}, {15, 15}};
      for (int[] num : input) {
         Instant start = Instant.now();
         int result = new Solution().numberOfPaths(num[0], num[1]);
         Instant finish = Instant.now();
         long timeElapsed = Duration.between(start, finish).toMillis();
         System.out.println("Total Number of paths for grid(" + num[0]+","+num[1] + ") = " + result + ",Total time taken = " + timeElapsed);
      }
   }
   public int numberOfPaths(int rowSize, int columnSize){
      return numberOfPaths(0,0,rowSize,columnSize);
   }
public int numberOfPaths(int row, int column, int rowSize, int columnSize){
      if(row > rowSize - 1 || column > columnSize -1){
         return 0;
      }
      if(row == rowSize - 1 && column == columnSize - 1 ){
         return 1;
      }   
      return numberOfPaths(row+1,column,rowSize,columnSize)+numberOfPaths(row,column+1,rowSize,columnSize);
   }
}

When you run this program you can see for higher values of grid, it takes a lot of time for the execution.

Sample output:

Total Number of paths for grid(3,3) = 6,Total time taken = 0
Total Number of paths for grid(6,5) = 126,Total time taken = 0
Total Number of paths for grid(15,15) = 40116600,Total time taken = 444

Question : In recursive flow, do you see any repeating sub problems?

Let us consider the tree again.

In the above tree if you notice, this solution is repeatedly calculating the total number of paths for same row, column combination.

For e.g (1,1)=> calculated two times.

Now you can think of some kind of a cache to save already calculated values.

What should be the key of the cache? We can use combination of row and column as key of the cache.

Enhanced Java Program using Memoization

public class Solution {
   public static void main(String[] args){
      int[][] input = {{3, 3}, {6, 5}, {15, 15}};
      for(int[] num : input) {
        Instant start = Instant.now();
        int result = new Solution().numberOfPaths(num[0],num[1]);
        Instant finish = Instant.now();
        long timeElapsed = Duration.between(start, finish).toMillis();
        System.out.println("fib("+num+") = "+result+",Total time taken = "+timeElapsed);
      } 
   }
public int numberOfPaths(int rowSize, int columnSize){
      Map<String,Integer> memo = new HashMap<>();
      return numberOfPaths(0,0,rowSize,columnSize,memo);
   }
public int numberOfPaths(int row, int column, int rowSize, int columnSize, Map<String,Integer> memo){
      String key = row+","+column;
      if(memo.containsKey(key)){
         return memo.get(key);
      }
      if(row > rowSize - 1 || column > columnSize -1){
         return 0;
      }
      if(row == rowSize - 1 && column == columnSize - 1 ){
         return 1;
      }   
      int result = numberOfPaths(row+1,column,rowSize,columnSize,memo)+numberOfPaths(row,column+1,rowSize,columnSize,memo);
      memo.put(key,result); 
      return result;
   }
}

Output:

Total Number of paths for grid(3,3) = 6,Total time taken = 0
Total Number of paths for grid(6,5) = 126,Total time taken = 0
Total Number of paths for grid(15,15) = 40116600,Total time taken = 1

Enhanced Time Complexity and Space Complexity

Time Complexity : O(m*n)
Space Complexity : O(m*n)

Variation of Grid Problem with Obstacle present in the Grid

There is another problem with slight variation of grid traveller problem. In this problem there can be one or more obstacles present in the grid.

For e.g. In the given grid, 0 can considered as a space and 1 can be considered as an obstacle. Find out the number of ways a robot can move from (0,0) to (2,2). The grid will be provided as input to the method.

Grid with obstacle.

Java Solution with Memoization

public class Solution {
   public static void main(String[] args){
      int[][] input = {{0,0,0,0},{0,0,0,1},{0,0,0,0}};
      Instant start = Instant.now();
      int result = new Solution().numberOfPathsWithObstacles(input);
      Instant finish = Instant.now();
      long timeElapsed = Duration.between(start, finish).toMillis();
      System.out.println("fib("+num+") = "+result+",Total time taken = "+timeElapsed);
      } 
   }
public int numberOfPathsWithObstacles(int[][] grid){
      Map<String,Integer> memo = new HashMap<>();
      return numberOfPathsWithObstacles(0,0,rowSize,columnSize,memo,grid);
   }
public int numberOfPathsWithObstacles(int row, int column, int rowSize, int columnSize, Map<String,Integer> memo,int[][] grid){
      String key = row+","+column;
      if(memo.containsKey(key)){
         return memo.get(key);
      }
      if(row > rowSize - 1 || column > columnSize -1 || grid[row][column]==1){
         return 0;
      }
      if(row == rowSize - 1 && column == columnSize - 1 ){
         return 1;
      }
int result = numberOfPaths(row+1,column,rowSize,columnSize,memo)+numberOfPaths(row,column+1,rowSize,columnSize,memo);
      memo.put(key,result); 
      return result;
}
}

The solution is similar to previous problem except we have added an additional condition grid[row][column] == 1 to check whether any obstacle present in current path. If you come across an obstacle we can say this path is not a valid one.

if(row > rowSize - 1 || column > columnSize -1 || grid[row][column]==1){
         return 0;
}

Happy Coding

Enjoy!!!