An Interest In:
Web News this Week
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
April 23, 2021 03:19 am GMT
Original Link: https://dev.to/cod3pineapple/leetcode-64-minimum-path-sum-javascript-solution-5b4o
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.
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]};
Original Link: https://dev.to/cod3pineapple/leetcode-64-minimum-path-sum-javascript-solution-5b4o
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To