Grid DP

Unique paths, minimum path sum, cherry pickup on grids.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Unique Paths

m×n grid, start at top-left, only move right or down. dp[i][j] = ways to reach (i,j) = dp[i-1][j] + dp[i][j-1]. Base: dp[0][j]=1, dp[i][0]=1.

Gounique-paths.go

15 linesLn 1, Col 1Go

Top row and left column are 1 (only one way). Each cell sums ways from top and left.

Minimum Path Sum

Grid with non-negative integers. Find path from top-left to bottom-right minimizing sum. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Gominimum-path-sum.go

17 linesLn 1, Col 1Go

Add current cell value to min of top or left path sum.

Cherry Pickup (Two Paths)

Two people start at (0,0), both go to (n-1,n-1), then return. Maximize cherries collected (cells with 1). Equivalent to two people going simultaneously from (0,0) to (n-1,n-1). 3D DP: dp[k][x1][x2] where k = step, x1,x2 = row positions (col = k-x).

Space Optimization

Most grid DP only needs previous row (or even 1D array). For unique paths: dp[j] = dp[j] + dp[j-1] (1D). For min path sum: same. Reduces O(mn) space to O(n).

Gogrid-dp-space-optimized.go

28 linesLn 1, Col 1Go

1D array processes row by row. dp[j] = current row's value, dp[j-1] = left neighbor (already updated for current row).

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.