64.Minimum Path Sum

tags: Medium,Array,Matrix,DP

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

Yen-Chi ChenMon, 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]

Yen-Chi ChenMon, 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]

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

MarsgoatMon, Mar 27, 2023

Reference

回到題目列表