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.

Get Kartik’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //approach
        //n,m - rows of matrix, column of matrix
        //n-1 to 0, m-1 to 0
        //result[n-1][m-1] = grid[x][y] + min (result[n-1][m-2], result[n-2][m-1]);
        
        int n = grid.size();
        int m = grid[0].size();

        for (int i = 0; i <= n-1; i++) {
            for (int j = 0; j <= m-1; j++) {
                int temp = grid[i][j];
                if (i-1 >= 0 && j-1 >= 0)
                grid[i][j] = min (grid[i-1][j], grid[i][j-1]);
                else if (i-1>=0) 
                grid[i][j] = grid[i-1][j];
                else if (j-1 >= 0)
                grid[i][j] = grid[i][j-1];
                else
                grid[i][j] = 0;
                grid[i][j] += temp;
            }
        }

        return grid[n-1][m-1];
    }
};

/**
recursive approach require 1 global variable

2,2 -> 2,1 1,2 -> 2,0 1,1 0,2 -> 1,0 0,1 -> 0,0
2,2 <- 2,1 1,2 <- 2,0 1,1 0,2 <- 1,0 0,1 <- 0,0


        .
    .       .
.       .       .
    .       .
        .

. . . . . - Iterate towards all values
. . . . .
. . . . .
. . . . .


grid
m*n
non negative number
top left -> bottom right
minimize the sum of all numbers
move only right or down

Total diff paths
start point - (0, 0)
end point - (n-1, n-1)

approach consist of recursive approach as we need to minimize the sum
block (x, x) = min (block (x, x-1), block (x-1, x)) + val(x, x)
This return one possible scenario that is there are repetitive results and to approach this problem 
There are 2 possible either remove all the repetitive work or consider it.
Repetitive element
block(x-1, x) = min (block(x-2, x), block(x-1, x-1)) + val(x-1, x);
block(x, x-1) = min (block(x, x-2), block(x-1, x-1)) + val(x, x-1);
Common Element: block(x-1, x-1);
Non Common Element: block (x-2, x) n block (x, x-2)

One approach Store values -- memory consumptions
Another way ?:
block (x, x) depends on block (x-1, x-1) n non common elements
...

Recommended approach
j = 0,1,2,3,4...
iniresult = 0;
target - ways[i]? target = ways[n]
result = min (ways[n-1] - possible) + val[i-1]; 
Top Down 
for (int j = 0; j < ways.size(); ++j) {
    result = min (result, topDown(target - ways[j]) + cost/ path/ sum);
}
return memo[state params] = result

Bottom up
i = 1, 2, 3, 5
for (int i = 1; i <= target; ++i) {
    for (int j = 0; j < ways.size(); ++j) {
        dp[i] = min (dp[i], dp[i-ways[i]] + cost / path / sum)
    }
}
*/

Imp links:
Problem:https://leetcode.com/problems/minimum-path-sum/?envType=list&envId=55ac4kuc

Similar Problem:https://leetcode.com/list/55ac4kuc/

DP Pattern:https://leetcode.com/discuss/study-guide/458695/Dynamic-Programming-Patterns