LeetCode 64. Minimum Path Sum (javascript solution)

Description:

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.


This content originally appeared on DEV Community and was authored by codingpineapple

Description:

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.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var minPathSum = function(grid) {
    // Create table
    const dp = new Array(grid.length).fill(0).map(() => Array(grid[0].length).fill(Infinity));
    // Add starting value
    dp[0][0] = grid[0][0]
    // Populate table
    for (let i = 0; i < dp.length; i++) {
        for(let j = 0; j < dp[0].length; j++) {
            // Add current cell total to cells to the right and below if the current cell + grid value of cell right/below is less than that cell's current total
            if(i+1 < dp.length) dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+grid[i+1][j])
            if(j+1 < dp[0].length) dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+grid[i][j+1])
        }
    }
    return dp[dp.length-1][dp[0].length-1]
};


This content originally appeared on DEV Community and was authored by codingpineapple


Print Share Comment Cite Upload Translate Updates
APA

codingpineapple | Sciencx (2021-04-23T03:19:03+00:00) LeetCode 64. Minimum Path Sum (javascript solution). Retrieved from https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/

MLA
" » LeetCode 64. Minimum Path Sum (javascript solution)." codingpineapple | Sciencx - Friday April 23, 2021, https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/
HARVARD
codingpineapple | Sciencx Friday April 23, 2021 » LeetCode 64. Minimum Path Sum (javascript solution)., viewed ,<https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/>
VANCOUVER
codingpineapple | Sciencx - » LeetCode 64. Minimum Path Sum (javascript solution). [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/
CHICAGO
" » LeetCode 64. Minimum Path Sum (javascript solution)." codingpineapple | Sciencx - Accessed . https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/
IEEE
" » LeetCode 64. Minimum Path Sum (javascript solution)." codingpineapple | Sciencx [Online]. Available: https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/. [Accessed: ]
rf:citation
» LeetCode 64. Minimum Path Sum (javascript solution) | codingpineapple | Sciencx | https://www.scien.cx/2021/04/23/leetcode-64-minimum-path-sumjavascript-solution/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.