Explain the grid paths DP.
Skip to solutionKEEP THE
mediumDSA
How do you count unique paths in a grid?
624 views
01
Understand the problem
dpgrid
02
Attempt it yourself
Sketch your approach before reading the solution — that's what interviews test.
Nudge consolestandby
Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.
03
Study the solution
Moving only right or down, the number of paths to a cell is paths(up) + paths(left), with edges initialized to 1. Fill the grid bottom-up in O(m×n), reducible to O(n) with a single row. Closed form: C(m+n-2, m-1).
Solution ready — 2 min read
Classified // press E to declassify
04
Read the code
Rolling 1-D DP
Run Playgrounddef unique_paths(m, n):
dp = [1] * n # top row: one way to each cell
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1] # from above (dp[j]) + from the left (dp[j-1])
return dp[n - 1]
# --- demo ---
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 2)) # 305
Join the discussion
Discussion (0)
Sign in to join the discussion.
No responses yet. Be the first to share what you think.
Transmission complete // awaiting log
KEEP THE
STREAK ALIVE.
Dossier 60 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.