Given an m x n grid of non-negative numbers, find a path from the top-left to the bottom-right cell that minimises the sum of all numbers on it, moving only right or down. Return that minimum sum.
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every right/down path is exponential. State: dp[r][c] = minimum path sum from the start to (r, c). Recurrence: the path arrived from above or from the left, so dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]). Base cases: dp[0][0] = grid[0][0]; the first row can only come from the left and the first column only from above, so they are prefix sums. The memoised recursion and the bottom-up table both cost O(m * n), and one row array is enough because each row only reads the row above.
Algorithm
- Create
dpof lengthn; fill it with the prefix sums of the first row. - For each next row
r, first setdp[0] += grid[r][0](only from above). - For
cfrom 1 ton - 1, setdp[c] = grid[r][c] + min(dp[c], dp[c - 1]), wheredp[c]is still the value from above. - Return
dp[n - 1].
O(m * n)Space: O(n)class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] for c in range(1, n): dp[c] = dp[c - 1] + grid[0][c] # first row for r in range(1, m): dp[0] += grid[r][0] # first column for c in range(1, n): dp[c] = grid[r][c] + min(dp[c], dp[c - 1]) # above vs left return dp[n - 1]