Grid Paths Problem

and Dynamic Programming Solution to it using memoization and tabulation in Rust Language.

Introduction

Grid Paths is another Dynamic Problem based on grids.

In this problem, you are given a grid with traps / obstacles. You have to tell the number of unique paths to reach from top left to bottom right in the grid, without stepping onto trap.

You can only move in right and down directions.

This problem is taken from CSES Problem Set

In the grid, `.` denotes an empty cell, and `*` denotes a trap.

So, for above grid, answer is 3

Recursive Solution

In recursive solution, we start from the end, that is, bottom right cell, and take sum of paths of cell upwards and leftwards to it.

If the cell is `*` in the grid, we return 0.

Algorithm

1. If the value of cell in grid is `*`, return 0.
2. Base Case would be that, if the current grid has 1 column and 1 row, return 1.
3. If current Grid has 1 row, we can traverse only leftwards. So, return Grid Paths of the left cell.
4. Similarly, If current Grid has 1 column, we can traverse only upwards. So, return Grid Paths of the upper cell.
5. Else, return the sum of Grid Paths of left and upper cells.

Function

Here is the function using above algorithm

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize) -> usize{    // If there is no row or column in the grid, return 0    if r<1 || c < 1 { return 0; }
// If corresponding grid value is *, return 0    if grid[r-1][c-1] == '*' { return 0;}
// Base Case    // If only 1 row and column, return 1    if r == 1 && c==1 { return 1; }
// Recursive Cases    // If only 1 row, can go only left    if r == 1 { return grid_paths(grid, 1, c-1); }
// If only 1 column, can go only up    if c == 1 { return grid_paths(grid, r-1, 1); }
// Else, return sum of upper and left values    return grid_paths(grid, r-1, c) + grid_paths(grid, r, c-1);}```

With Driver code

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize) -> usize{    // If there is no row or column in the grid, return 0    if r<1 || c < 1 { return 0; }
// If corresponding grid value is *, return 0    if grid[r-1][c-1] == '*' { return 0;}
// Base Case    // If only 1 row and column, return 1    if r == 1 && c==1 { return 1; }
// Recursive Cases    // If only 1 row, can go only left    if r == 1 { return grid_paths(grid, 1, c-1); }
// If only 1 column, can go only up    if c == 1 { return grid_paths(grid, r-1, 1); }
// Else, return sum of upper and left values    return grid_paths(grid, r-1, c) + grid_paths(grid, r, c-1);}
// Driver Code
fn main() {    // Take the sample grid, as shown in picture    let grid = vec![        vec!['.', '.', '.', '.', '.'],        vec!['.', '*', '.', '*', '.'],        vec!['.', '.', '.', '.', '.'],    ];
// Print The number of paths of the grid    println!("{}", grid_paths(&grid, grid.len(), grid[0].len()));}```

Output

3

Time Complexity : O( 2r+c )
Space Complexity : O( r+c )

( Space complexity includes recursive stack space )

Overlapping Sub-problems

If we have a look carefully on recursive approach, we computed multiple results many times.

For example : In a 20×20 grid, you can reach the (10, 10) cell in thousands of ways, and takes thousands of recursions each time to calculate.

These are called Overlapping Sub-problems because they are smaller part of large problems, and are computed again and again.

So, we simply calculate them once, and store it in a matrix, and retrieve it when necessary. This helps to save a lot of computation.

This is called Dynamic Programming Approach for the problem.

Memoization ( Top-down DP ) Method

In memoization method, we simply take a DP matrix, and store the computed result.

Algorithm

1. Initially, take a DP matrix and set all its elements to `None` type. Alternatively, you can set it to -1.
2. If the grid paths are already calculated, that is given index of matrix is `Some` or not -1, return it.
3. Else, calculate the grid paths by using recursion and store it in the DP matrix.

Function

Here is the function using above algorithm

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize,  dp:&mut Vec<Vec<Option<usize>>>) -> usize{    // If there is no row or column in the grid, return 0    if r<1 || c < 1 { return 0; }
// If already computed, return value    if dp[r-1][c-1].is_some() { return dp[r-1][c-1].unwrap(); }
// If corresponding grid value is *, return 0    if grid[r-1][c-1] == '*' { dp[r-1][c-1] = Option::from(0); return 0;}
// Base Case    // If only 1 row and column, return 1    if r == 1 && c==1 { dp[0][0] = Option::from(1); return 1; }
// Recursive Cases    // If only 1 row, can go only left    if r == 1 { dp[0][c-1] = Option::from(grid_paths(grid, 1, c-1, dp)); return dp[0][c-1].unwrap(); }
// If only 1 column, can go only up    if c == 1 { dp[r-1][0] = Option::from( grid_paths(grid, r-1, 1, dp)); return dp[r-1][0].unwrap(); }
// Else, return sum of upper and left values    dp[r-1][c-1] = Option::from(grid_paths(grid, r-1, c, dp) + grid_paths(grid, r, c-1, dp));    return dp[r-1][c-1].unwrap();}```

With Driver code

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize,  dp:&mut Vec<Vec<Option<usize>>>) -> usize{    // If there is no row or column in the grid, return 0    if r<1 || c < 1 { return 0; }
// If already computed, return value    if dp[r-1][c-1].is_some() { return dp[r-1][c-1].unwrap(); }
// If corresponding grid value is *, return 0    if grid[r-1][c-1] == '*' { dp[r-1][c-1] = Option::from(0); return 0;}
// Base Case    // If only 1 row and column, return 1    if r == 1 && c==1 { dp[0][0] = Option::from(1); return 1; }
// Recursive Cases    // If only 1 row, can go only left    if r == 1 { dp[0][c-1] = Option::from(grid_paths(grid, 1, c-1, dp)); return dp[0][c-1].unwrap(); }
// If only 1 column, can go only up    if c == 1 { dp[r-1][0] = Option::from( grid_paths(grid, r-1, 1, dp)); return dp[r-1][0].unwrap(); }
// Else, return sum of upper and left values    dp[r-1][c-1] = Option::from(grid_paths(grid, r-1, c, dp) + grid_paths(grid, r, c-1, dp));    return dp[r-1][c-1].unwrap();}
// Driver Code
fn main() {    // Take the sample grid, as shown in picture    let grid = vec![        vec!['.', '.', '.', '.', '.'],        vec!['.', '*', '.', '*', '.'],        vec!['.', '.', '.', '.', '.'],    ];
// Initialize DP matrix    let mut dp = vec![vec![None; grid[0].len()]; grid.len()];
// Print The number of paths of the grid    println!("{}", grid_paths(&grid, grid.len(), grid[0].len(), &mut dp));}```

Output

3

Time Complexity : O( r*c )
Space Complexity : O( r*c )

Tabulation ( Bottom-up DP ) Method

Although time and space complexities of tabulation as well as memoization method are same, tabulation is much more efficient as there are a lot of expensive recursive calls in memoization.

In tabulation method, we make the DP matrix, and fill it first on the basis of base condition, and then on the basis of previous row.

Algorithm

1. Initially, set `1` upto first `*` in first row and column in DP matrix, and 0 after that.
2. Now, for each of cell, if the corresponding cell in original grid is `*`, set it to 0, else sum of upper and left cell in DP matrix.
3. Finally, return the value of last cell as the answer.

Function

Here is the function using above algorithm

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize,  dp:&mut Vec<Vec<Option<usize>>>) -> usize{
// Set the value in the first row upto first * as 1    // Trapped variable stores whether * has come    let mut trapped = false;    for i in 0..c {        if grid[0][i] == '*' { trapped = true; }        // If * has already come        if trapped { dp[0][i] = Option::from(0); }        else { dp[0][i] = Option::from(1); }    }
// Set the value in the first column upto first * as 1    trapped = false;    for i in 0..r {        if grid[i][0] == '*' { trapped = true; }        // If * has already come        if trapped { dp[i][0] = Option::from(0); }        else { dp[i][0] = Option::from(1); }    }
for i in 1..r {        for j in 1..c {            // If *, set dp[i][j] = 0            if grid[i][j] == '*' { dp[i][j] = Option::from(0); continue; }
// Set sum of paths of upper and left cell            dp[i][j] = Option::from(dp[i-1][j].unwrap() + dp[i][j-1].unwrap() );        }    }
// Return last value as answer    return dp[r-1][c-1].unwrap();}```

Use the same driver code.

Output

3

Time Complexity : O( r*c )
Space Complexity : O( r*c )

Conclusion

Grid Paths is a grid based Dynamic Programming problem.

In this problem, you are given a grid with traps / obstacles. You have to tell the number of unique paths to reach from top left to bottom right in the grid, without stepping onto trap.

You can only move in right and down directions.

In this article, we saw how to solve the Grid Paths problem, first using recursion and then using Dynamic Programming, memoization as well as tabulation method in Rust Language.

Here is the optimized function for easy access

```fn grid_paths(grid:&Vec<Vec<char>>, r:usize, c:usize,  dp:&mut Vec<Vec<Option<usize>>>) -> usize{    let mut trapped = false;    for i in 0..c {        if grid[0][i] == '*' { trapped = true; }        if trapped { dp[0][i] = Option::from(0); }  else { dp[0][i] = Option::from(1); } }
trapped = false;    for i in 0..r {        if grid[i][0] == '*' { trapped = true; }        if trapped { dp[i][0] = Option::from(0); } else { dp[i][0] = Option::from(1); } }
for i in 1..r { for j in 1..c {            if grid[i][j] == '*' { dp[i][j] = Option::from(0); continue; }            dp[i][j] = Option::from(dp[i-1][j].unwrap() + dp[i][j-1].unwrap() ); } }    return dp[r-1][c-1].unwrap();}```