Minimum Path Sum

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

Introduction

Minimum Path Sum, also known as Minimum Cost Path, is a grid based Dynamic Programming problem. In this problem, you are given a grid of positive numbers, and you have to tell the minimum sum of elements from top left corner to bottom right through any path, but you can move only rightwards or downwards.

So, for above grid, answer is 22

Recursive Solution

In recursive solution, we start from the end, that is, bottom right cell, and take minimum of Minimum Path Sum of the cell upwards and leftwards to it.

So, we find the Minimum Path Sum of upward and leftward cell and return this after adding the cost of current cell.

Algorithm

Base Case would be that, if the current grid has 1 column and 1 row, return value of current cell.
If current Grid has 1 row, we can traverse only leftwards. So, return cost of current cell + cost of Minimum Path Sum of the left cell.
Similarly, if the grid has only 1 column, return cost of current cell + cost of Minimum Path Sum of the upward cell.
Else, return the cost of current cell + minimum of Minimum Path Sum of the upward cell and leftward cell.

Function

Here is the function using above algorithm

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize) -> usize {

    // Base Case, if only 1 row and column, return the value of top left cell
    if r == 1 && c ==1 { return grid[0][0]; }

    // If only 1 row, we can only move leftwards
    if r==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r, c-1 ) ;}

    // If only 1 column, we can only move upwards
    if c==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r-1, c ); }

    // Else, we take minimum of both leftwards path and rightwards path
    return grid[r-1][c-1] + min(minimum_cost_path(grid,r-1, c ) , minimum_cost_path(grid,r, c-1 ));
}

With Driver code

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize) -> usize {

    // Base Case, if only 1 row and column, return the value of top left cell
    if r == 1 && c ==1 { return grid[0][0]; }

    // If only 1 row, we can only move leftwards
    if r==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r, c-1 ) ;}

    // If only 1 column, we can only move upwards
    if c==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r-1, c ); }

    // Else, we take minimum of both leftwards path and rightwards path
    return grid[r-1][c-1] + min(minimum_cost_path(grid,r-1, c ) , minimum_cost_path(grid,r, c-1 ));
}

// Driver Code

fn main() {
    let grid = vec![
        vec![2, 4, 1, 5, 6],
        vec![3, 3, 2, 6, 7],
        vec![1, 4, 5, 3, 5],
    ];
    println!("{}", minimum_cost_path(&grid, grid.len(), grid[0].len()));
}

Output

22

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

( Space complexity includes recursive stack space )

Note : Space complexity is 2^r+c because each time, we have 2 choices.

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

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

Function

Here is the function using above algorithm

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize, dp:&mut Vec<Vec<Option<usize>>>) -> usize {

    // If Already computed, return it
    if dp[r-1][c-1].is_some() { return dp[r-1][c-1].unwrap(); }

    // Base Case, if only 1 row and column, return the value of top left cell
    if r == 1 && c ==1 { dp[0][0] = Option::from(grid[0][0]) ;return dp[0][0].unwrap();  }

    // If only 1 row, we can only move leftwards
    if r==1 { dp[0][c-1] = Option::from(grid[0][c-1] + minimum_cost_path(grid,1, c-1 , dp)) ; return dp[0][c-1].unwrap();}

    // If only 1 column, we can only move upwards
    if c==1 { dp[r-1][0] = Option::from(grid[r-1][0] + minimum_cost_path(grid,r-1, 1 , dp)) ; return dp[r-1][0].unwrap();}

    // Else, we take minimum of both leftwards path and rightwards path
    dp[r-1][c-1] = Option::from( grid[r-1][c-1] + min(minimum_cost_path(grid,r-1, c, dp ) , minimum_cost_path(grid,r, c-1, dp)) );

    return dp[r-1][c-1].unwrap();
}

With Driver code

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize, dp:&mut Vec<Vec<Option<usize>>>) -> usize {

    // If Already computed, return it
    if dp[r-1][c-1].is_some() { return dp[r-1][c-1].unwrap(); }

    // Base Case, if only 1 row and column, return the value of top left cell
    if r == 1 && c ==1 { dp[0][0] = Option::from(grid[0][0]) ;return dp[0][0].unwrap();  }

    // If only 1 row, we can only move leftwards
    if r==1 { dp[0][c-1] = Option::from(grid[0][c-1] + minimum_cost_path(grid,1, c-1 , dp)) ; return dp[0][c-1].unwrap();}

    // If only 1 column, we can only move upwards
    if c==1 { dp[r-1][0] = Option::from(grid[r-1][0] + minimum_cost_path(grid,r-1, 1 , dp)) ; return dp[r-1][0].unwrap();}

    // Else, we take minimum of both leftwards path and rightwards path
    dp[r-1][c-1] = Option::from( grid[r-1][c-1] + min(minimum_cost_path(grid,r-1, c, dp ) , minimum_cost_path(grid,r, c-1, dp)) );

    return dp[r-1][c-1].unwrap();
}

// Driver Code

fn main() {
    let grid = vec![
        vec![2, 4, 1, 5, 6],
        vec![3, 3, 2, 6, 7],
        vec![1, 4, 5, 3, 5],
    ];

    // Initialize DP matrix
    let mut dp = vec![vec![Option::None; grid[0].len()]; grid.len()];

    println!("{}", minimum_cost_path(&grid, grid.len(), grid[0].len(), &mut dp));
}

Output

22

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

Initialize the first row and first column like Prefix Sum Array, because to reach to given cell in first row or column, we have only 1 path, rightwards in case of row and downwards in case of column.
For all cells in DP matrix, set its value to the sum of its corresponding value in initial grid and minimum of adjacent left and up cell.
Finally, return the bottom right value of the DP matrix.

Function

Here is the function using above algorithm

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize, dp:&mut Vec<Vec<Option<usize>>>) -> usize {

    // Set dp[0][0], the first element of DP matrix as corresponding grid value.
    dp[0][0] = Option::from(grid[0][0]);

    // Initialize the first row and column of the DP matrix
    for i in 1..r { dp[i][0] = Option::from(dp[i-1][0].unwrap() + grid[i][0]); }
    for i in 1..c { dp[0][i] = Option::from(dp[0][i-1].unwrap() + grid[0][i]); }

    // Traverse for each Row and column
    for i in 1..r {
        for j in 1..c {
            // Set dp[i][j] as sum of corresponding grid value and
            // Minimum of minimum path sum of upper and left cell
            dp[i][j] = Option::from(grid[i][j] + min(dp[i-1][j].unwrap(), dp[i][j-1].unwrap()));
        }
    }

    // Finally, Return last element
    return dp[r-1][c-1].unwrap();
}

Use the same driver code.

Output

22

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

Conclusion

Minimum Path Sum, also known as Minimum Cost Path, is a grid based Dynamic Programming problem.

In this problem, you are given a grid of positive numbers, and you have to tell the minimum sum of elements from top left corner to bottom right through any path, but you can move only rightwards or downwards.

In this article, we saw how to solve the Minimum Path Sum 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

use std::cmp::min;

pub fn minimum_cost_path(grid: &Vec<Vec<usize>>, r:usize, c:usize, dp:&mut Vec<Vec<Option<usize>>>) -> usize {
    dp[0][0] = Option::from(grid[0][0]);
    for i in 1..r { dp[i][0] = Option::from(dp[i-1][0].unwrap() + grid[i][0]); }
    for i in 1..c { dp[0][i] = Option::from(dp[0][i-1].unwrap() + grid[0][i]); }
    for i in 1..r {
        for j in 1..c {
            dp[i][j] = Option::from(grid[i][j] + min(dp[i-1][j].unwrap(), dp[i][j-1].unwrap())); }}
    return dp[r-1][c-1].unwrap();
}

Thank You