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.
We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix .
\nThe 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\nComplexity Analysis
\nAlgorithm
\nWe 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.
\nThe following figure illustrates the process:\n\n!?!../Documents/64_Minimum_Path_Sum.json:859,390!?!
\n\nComplexity Analysis
\nTime complexity : . We traverse the entire matrix once.
\nSpace complexity : . Another matrix of the same size is used.
\nAlgorithm
\nIn 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
\nWe repeat the same process for every row as we move upwards. At the end gives the\n required minimum sum.
\n\nComplexity Analysis
\nTime complexity : . We traverse the entire matrix once.
\nSpace complexity : . Another array of row size is used.
\nAlgorithm
\nThis 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\nComplexity Analysis
\nTime complexity : . We traverse the entire matrix once.
\nSpace complexity : . No extra space is used.
\nAnalysis written by: @vinod23
\n