find minimum sum path from top-left to bottom-right using dynamic programming with space optimization.
dp[i][j] = minimum sum to reach (i,j). can only move right or down. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
optimize space to O(n) by using only one row. update row from left to right, carrying previous row values.
since we only need previous row and current position, we can use single array and update in-place. reduces space from O(mn) to O(n).
O(mn) time, O(n) space where m and n are grid dimensions. efficient dp solution.
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid or not grid[class="syntax-number">0]:
return class="syntax-number">0
rows, cols = len(grid), len(grid[class="syntax-number">0])
dp = [class="syntax-number">0] * cols
running = class="syntax-number">0
for c in range(cols):
running += grid[class="syntax-number">0][c]
dp[c] = running
for r in range(class="syntax-number">1, rows):
dp[class="syntax-number">0] += grid[r][class="syntax-number">0]
for c in range(class="syntax-number">1, cols):
dp[c] = min(dp[c], dp[c - class="syntax-number">1]) + grid[r][c]
return dp[-class="syntax-number">1]