문제

양수로 이루어진 m x n 그리드를 인자로 준다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때, 가장 작은 합을 찾아서 return 하라. 한 지점에서 우측이나 아래로만 이동할 수 있다.

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

Output: 7

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

Thinking Algorithm

1. 갈 수 있는 방향은 오른쪽과 아래뿐
2. 아래로 가는 경우를 먼저 작성 더 아래에 있는 것과 그 위의 것의 합을 구함
3. 오른쪽으로 가는 경우도 마찬가지로 더 오른쪽에 있는 것과 그 전의 것의 합을 구함
4. 오른쪽과 아래로 가는 것의 합 중 더 작은 것을 구해 더해줌
5. 그리드 가장 오른쪽 하단의 값을 반환

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];
};