64.Minimum Path Sum
===

###### tags: `Medium`,`Array`,`Matrix`,`DP`

[64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)

### 題目描述

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

### 解答
#### C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) ;
                else if (i == 0) grid[i][j] += grid[i][j-1];
                else if (j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
};

> [name=Yen-Chi Chen][time=Mon, Mar 27, 2023]

#### Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0: pass
                elif i == 0: grid[i][j] += grid[i][j-1]
                elif j == 0: grid[i][j] += grid[i-1][j]
                else: grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

> [name=Yen-Chi Chen][time=Mon, Mar 27, 2023]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dist = [[-1 for col in grid[0]] for row in grid]
        dist[0][0] = grid[0][0]
        for i, col in enumerate(grid[0][1:]):
            dist[0][i+1] = col + dist[0][i]
        for i, row in enumerate(grid[1:]):
            dist[i+1][0] = row[0] + dist[i][0]

        for i, row in enumerate(dist[1:]):
            for j, col in enumerate(dist[i][1:]):
                dist[i+1][j+1] = min(dist[i][j+1], dist[i+1][j]) + grid[i+1][j+1]
        return dist[-1][-1]

> [name=gpwork4u][time=Mon, Mar 27, 2023]

#### Javascript

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const isInBound = (i, j) => i >= 0 && i < m && j >= 0 && j < n;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const top = isInBound(i - 1, j) ? grid[i - 1][j] : Infinity;
      const left = isInBound(i, j - 1) ? grid[i][j - 1] : Infinity;
      grid[i][j] += Math.min(top, left);
    }
  }

  return grid[m - 1][n - 1];
}

> [name=Marsgoat][time=Mon, Mar 27, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)