1. Problem Statement (Simple Explanation)
You have an m x n grid:
Start at top-left: (0, 0)
Goal is bottom-right: (m-1, n-1)
At each step you can move only right or down.
You must return the number of unique paths from start to goal.
Answer is guaranteed ≤ 2 * 109.
2. Examples
Example 1:
Input: m = 3, n = 7
There are 28 distinct paths.
Output: 28
Example 2:
Input: m = 3, n = 2
Paths:
Right → Down → Down
Down → Down → Right
Down → Right → Down
Total = 3.
Output: 3
3. Approach 1 – Dynamic Programming (O(m·n))
Let dp[i][j] = number of unique paths to reach cell (i, j).
Rules:
Only move right or down:
To reach (i, j), you can come from:
(i-1, j) (from above)
(i, j-1) (from left)
So: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Base cases:
First row i = 0:
You can only move right, so dp[0][j] = 1 for all j.
First column j = 0:
You can only move down, so dp[i][0] = 1 for all i.
Answer:
dp[m-1][n-1].
We can compress to 1D array (dp[j] for current row) to get O(n) space.
Pseudo-code (1D DP):
Explanation:
dp[j] holds the number of ways to reach cell (i, j) in the current row.
dp[j] (old) = ways from above (dp[j]).
dp[j-1] = ways from left.
Complexity:
Time: O(m⋅n)
Space: O(n) (or O(m⋅n) if using full 2D DP)
4. Approach 2 – Combinatorics (Binomial Coefficient)
Total moves:
To go from (0,0) to (m-1,n-1) you must make:
(m-1) down moves and (n-1) right moves, in any order.
Total steps: steps = (m-1) + (n-1) = m + n - 2.
Number of unique paths = number of ways to choose which of those steps are, say, right moves:
C(steps, right_moves) = C(m + n - 2, n - 1) = C(m + n - 2, m - 1)
Where C(a, b) is the binomial coefficient ("a choose b").
We can compute this iteratively without overflow within the constraints:
Compute product in double or 64-bit integer carefully.
But DP is straightforward and safe within the constraints, so use DP unless you’re explicitly asked to use combinatorics.
5. Java code
7. C++ code
8. Python code
9. JavaScript code
Comments
Post a Comment