[Programming Problem] 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:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12

[Problem Link]

Memoize by simply storing the minimum path to a cell via the top or left cell.

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

Memoized:
[[ 1, 4, 5 ],
[ 2, 7, 6 ],
[ 6, 8, 7 ]]

Solution will be the bottom right cell in the memoized array.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let ret = new Array(grid.length).fill(0).map((x) => new Array(grid[0].length).fill(0));
    for ( let i = 0 ; i < grid.length ; i++ ) {
        for ( let j = 0 ; j < grid[0].length ; j++ ) {
            if (i===0 && j===0) ret[i][j] = grid[i][j];
            else if (i===0) ret[i][j] = grid[i][j] + ret[i][j-1];
            else if (j===0) ret[i][j] = grid[i][j] + ret[i-1][j];
            else ret[i][j] = grid[i][j] + Math.min(ret[i-1][j], ret[i][j-1]);
        }
    }
    return ret[grid.length-1][grid[0].length-1];
};

softwareeveryday

204 thoughts on “[Programming Problem] Minimum Path Sum”

  18. I simply needed to say thanks once again. I am not sure the things that I would’ve sorted out in the absence of the type of smart ideas provided by you over this area. It actually was a very troublesome problem in my view, but finding out your expert approach you handled the issue took me to weep for happiness. I am thankful for the guidance and thus hope that you recognize what a powerful job that you are doing training some other people thru your websites. Most probably you’ve never encountered any of us.

    Reply

  19. My wife and i felt so comfortable Louis managed to conclude his investigations via the precious recommendations he obtained in your site. It is now and again perplexing just to possibly be giving for free tricks which often other people could have been selling. We really already know we need you to appreciate because of that. The type of explanations you made, the straightforward web site menu, the relationships you can make it easier to promote – it is most amazing, and it’s really leading our son and us believe that that topic is brilliant, which is certainly incredibly fundamental. Thank you for everything!

    Reply

  20. I have to show my affection for your kind-heartedness giving support to folks who actually need help with that concept. Your real dedication to passing the solution along was exceedingly important and have constantly empowered regular people much like me to reach their endeavors. Your amazing valuable tutorial can mean a lot to me and still more to my office colleagues. Warm regards; from each one of us.

    Reply

  23. I would like to show my affection for your kindness in support of those people that require help on your idea. Your personal dedication to passing the solution along has been really advantageous and has permitted people like me to reach their endeavors. Your entire warm and helpful guide indicates a lot to me and further more to my peers. With thanks; from each one of us.

    Reply

  24. I wanted to post a quick word to say thanks to you for all the fantastic tips and hints you are showing on this site. My time-consuming internet look up has now been honored with incredibly good tips to share with my pals. I ‘d tell you that most of us visitors are really blessed to live in a fine website with very many lovely people with beneficial tips and hints. I feel quite fortunate to have encountered the weblog and look forward to plenty of more pleasurable minutes reading here. Thanks once again for all the details.

    Reply

  32. Thanks so much for giving everyone a very brilliant chance to read critical reviews from here. It can be so sweet and also jam-packed with fun for me and my office colleagues to search your website not less than thrice a week to read through the fresh secrets you have got. And of course, I’m usually astounded considering the unique techniques you give. Selected two areas on this page are clearly the very best we’ve ever had.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More