Unique Paths: From Grid DP to a Single Binomial Coefficient
Unique Paths counts the ways a robot can move from the top-left to the bottom-right of an m x n grid, moving only right or down. It is a good problem to show three levels of solution in one answer.
Level 1: 2D DP
Each cell can be reached from the cell above or the cell to the left, so dp[r][c] = dp[r-1][c] + dp[r][c-1], with the first row and column equal to 1.
Level 2: one row
Only the previous row is ever read, so keep a single array and update it left to right.
Level 3: combinatorics
Every path is a sequence of m-1 downs and n-1 rights, so the answer is C(m+n-2, m-1). In Python, math.comb(m + n - 2, m - 1) returns it exactly. Mention overflow if the interviewer wants a fixed-width language and compute the product incrementally, dividing as you go.
Follow-ups
Unique Paths II adds obstacles: set dp to 0 on blocked cells and the formula no longer applies. Minimum Path Sum keeps the same shape with min instead of plus. Saying which follow-ups break the closed form shows depth.
If you want prompts while practising multi-level answers, try the interview copilot app we build at Linkjob AI. Disclosure: I help build Linkjob AI.