The Number of Ways to Reach Destination in the Grid problem asks you to count paths from the top-left to the bottom-right of an n×m grid where you can only move right or down. This is the classic combinatorics problem: the answer is C(n+m-2, n-1) — choosing which steps are "down" from the total steps. The math, combinatorics, and dynamic programming interview pattern is demonstrated.
Uber asks this to test combinatorial reasoning vs DP reasoning. Knowing the closed-form formula C(n+m-2, n-1) demonstrates mathematical insight; being able to derive it via DP shows algorithmic thinking. Both approaches should be presented.
Combinatorics formula: Total steps = (n-1) down + (m-1) right = n+m-2 steps. Choose which n-1 are "down" → C(n+m-2, n-1).
DP alternative: dp[i][j] = paths to cell (i,j) = dp[i-1][j] + dp[i][j-1]. Base: dp[0][j] = dp[i][0] = 1. Return dp[n-1][m-1].
n=3, m=3. C(3+3-2, 3-1) = C(4,2) = 6. DP: dp = [[1,1,1],[1,2,3],[1,3,6]]. dp[2][2] = 6. ✓
Always know both the DP and combinatorial approaches for grid path counting. The formula C(n+m-2, n-1) is elegant and O(min(n,m)) to compute using Pascal's triangle or modular inverse. The DP is O(n*m) and extends to grids with obstacles. For interviews, state both, derive one from first principles, and discuss when each is preferable. Modular inverse computation (for large modulo) is a required companion skill.
