## 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

[[1,3,1],
[1,5,1],
[4,2,1]]

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

b'
\n\n

## Summary

\n

We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix .

\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards and find the minimum sum out of those two. It specifies whether we need to take a right step or downward step to minimize the sum.

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• Time complexity : . For every move, we have atmost 2 options.
• \n
• Space complexity : . Recursion of depth .
• \n
\n
\n

#### Approach #2 Dynamic Programming 2D [Accepted]

\n

Algorithm

\n

We use an extra matrix of the same size as the original matrix. In this matrix, represents the minimum sum of the path from the index to\nthe bottom rightmost element. We start by initializing the bottom rightmost element\nof as the last element of the given matrix. Then for each element starting from\nthe bottom right, we traverse backwards and fill in the matrix with the required\nminimum sums. Now, we need to note that at every element, we can move either\nrightwards or downwards. Therefore, for filling in the minimum sum, we use the\nequation:

\n

\n\n

\n

, taking care of the boundary conditions.

\n

The following figure illustrates the process:\n\n!?!../Documents/64_Minimum_Path_Sum.json:859,390!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse the entire matrix once.

\n
• \n
• \n

Space complexity : . Another matrix of the same size is used.

\n
• \n
\n
\n

#### Approach #3 Dynamic Programming 1D [Accepted]

\n

Algorithm

\n

In the previous case, instead of using a 2D matrix for dp, we can do the same\nwork using a array of the row size, since for making the current entry all we need is the dp entry for the bottom and\n the right element. Thus,\nwe start by initializing only the last element of the array as the last element of the given matrix.\nThe last entry is the bottom rightmost element of the given matrix. Then, we start\nmoving towards the left and update the entry as:

\n

\n\n

\n

We repeat the same process for every row as we move upwards. At the end gives the\n required minimum sum.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse the entire matrix once.

\n
• \n
• \n

Space complexity : . Another array of row size is used.

\n
• \n
\n
\n

#### Approach #4 Dynamic Programming (Without Extra Space) [Accepted]

\n

Algorithm

\n

This approach is same as Approach 2, with a slight difference. Instead of using\nanother matrix. We can store the minimum sums in the original matrix itself,\nsince we need not retain the original matrix here. Thus, the governing equation\nnow becomes:

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse the entire matrix once.

\n
• \n
• \n

Space complexity : . No extra space is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'