210901メッシュから最小和へのパス

質問する

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

Output: 7

googling正解

const minPathSum = grid => { 
    // 일단 첫 row와 첫 column은 각각, 그 path로 갔다고 생각하고 더해놓는다.
    for (let i = 1; i < grid.length; i++) {
        grid[i][0] += grid[i-1][0];      
    }
    
    for (let i = 1; i < grid[0].length; i++) {
         grid[0][i] += grid[0][i-1];
    }    
    
    for (let i = 1; i < grid.length; i++) {
        for (let j = 1; j < grid[0].length; j++) {
            
            //위쪽이나 왼쪽에서, 더 작은걸로 더해준다.
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[grid.length-1][grid[0].length-1];
};

console.log(minPathSum([[1,2,3],[4,1,2]])); // 6