# 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 cellif r == 1 && c ==1 { return grid[0][0]; }// If only 1 row, we can only move leftwardsif r==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r, c-1 ) ;}// If only 1 column, we can only move upwardsif 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 pathreturn 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 cellif r == 1 && c ==1 { return grid[0][0]; }// If only 1 row, we can only move leftwardsif r==1 { return grid[r-1][c-1] + minimum_cost_path(grid,r, c-1 ) ;}// If only 1 column, we can only move upwardsif 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 pathreturn grid[r-1][c-1] + min(minimum_cost_path(grid,r-1, c ) , minimum_cost_path(grid,r, c-1 ));}// Driver Codefn 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 itif 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 cellif 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 leftwardsif 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 upwardsif 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 pathdp[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 itif 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 cellif 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 leftwardsif 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 upwardsif 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 pathdp[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 Codefn main() {let grid = vec![vec![2, 4, 1, 5, 6],vec![3, 3, 2, 6, 7],vec![1, 4, 5, 3, 5],];// Initialize DP matrixlet 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 matrixfor 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 columnfor 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 celldp[i][j] = Option::from(grid[i][j] + min(dp[i-1][j].unwrap(), dp[i][j-1].unwrap()));}}// Finally, Return last elementreturn 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;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**