質問する

パラメータとして正数からなるm xnメッシュを用いた.上から左へ、下から右へ行くすべての要素を加えると、最小の和が見つかり、戻ります.1つの場所で右または下にしか移動できません.

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

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

Thinking Algorithm

が歩ける方向は右下角

のみです

未満の場合は、まず下と上の合計

を記入してください.

右に行く場合も同様で、もっと右のと前のを合わせて

を求めます

の右側と下の合計はより小さく、

を加えた.

グリッドの最右下隅の値

を返します.

Code

const minPathSum = grid => {
    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];
};