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
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
풀이
은찬
const minPathSum = (grid) => { const m = grid.length; const n = grid[0].length; const dp = Array.from({length: m}, () => Array(n).fill(0)); dp[0][0] = grid[0][0]; for(let i = 1; i < n; i++){ dp[0][i] = grid[0][i] + dp[0][i - 1]; } for(let i = 1; i < m; i++){ for(let j = 0; j < n; j++){ if(j === 0){ dp[i][j] = dp[i - 1][j] + grid[i][j]; } else{ dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]); } } } return dp[m - 1][n - 1]; };
재영
const minPathSum = (grid) => { const xLength = grid.length; const yLength = grid[0].length; const dp = Array.from({ length: xLength }, () => new Array(yLength).fill(Infinity) ); dp[0][0] = grid[0][0]; const directions = [ [-1, 0], [0, -1], ]; for (let i = 0; i < xLength; i += 1) { for (let j = 0; j < yLength; j += 1) { const now = grid[i][j]; for (let k = 0; k < 2; k += 1) { const [dx, dy] = directions[k]; const nx = i + dx; const ny = j + dy; if (nx >= 0 && ny >= 0 && nx < xLength && ny < yLength) { dp[i][j] = Math.min(dp[i][j], dp[nx][ny] + now); } } } } return dp[xLength - 1][yLength - 1]; };
효성
var minPathSum = function(grid) { const m = grid.length, n= grid[0].length; for(let i=1; i<m; i++) { grid[i][0] += grid[i-1][0]; } for(let i=1; i<n; i++) { grid[0][i] += grid[0][i-1]; } for(let i=1; i<m; i++) { for(let j=1; j<n; j++) { grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; };