Minimum Path Sum

Problem Id: 64 Difficulty: Medium Tag: Array Tag: Dynamic Programming


Intuition

This is a typical DP (Dynamic Programming) problem.

For each node x, y, the previous node must be either x - 1, y or x, y - 1. So the minimum steps is the min value of the minimum steps to get to x, y - 1 and the minimum steps to get to x - 1, y.

So we could solve this problem by top-down, left-right order of DP.

Solution


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [0] * n

        # Initial status, which is the first row
        dp[0] = grid[0][0]
        for j in range(1, n):
            dp[j] = dp[j - 1] + grid[0][j]

        # The main part of DP
        for i in range(1, m):
            dp[0] += grid[i][0]
            for j in range(1, n):
                dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]

        return dp[-1]