A robot stands on the top-left cell of an m x n grid and wants the bottom-right cell. It can only step right or down. Return how many distinct paths it can take.
Examples
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: right-down-down, down-right-down, down-down-right.
Example 3:
Input: m = 1, n = 1
Output: 1
Example 4:
Input: m = 10, n = 10
Output: 48620
Constraints
1 <= m, n <= 100
The answer fits in a 32-bit integer.
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Sum of the Two Ways In Optimal
Intuition
A cell is only reachable from above or from the left, so its path count is the sum of those two. The top row and left column have exactly one route each, which seeds everything. One row of counts, updated left to right, is enough — the value already in the array is "from above" and the value just written is "from the left".
Algorithm
1. Start a row of n ones: the first row's counts. 2. For each remaining row, walk left to right adding the value to the left. 3. The last cell holds the answer.
Time & Space
Time O(m*n). Space O(n). The closed form C(m+n-2, m-1) is worth mentioning; the DP is what the interview wants built.