Unique Paths
LeetCode #62 · Medium · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Top-Down DP with Memoization
Key insight
From any cell (i,j), the number of paths to the destination is the sum of paths from (i+1,j) and (i,j+1). This creates overlapping subproblems, making memoization effective.
Time
O(m * n)
Space
O(m * n)
Problem description(from LeetCode)
There is a robot on an m x n grid. The robot is initially located at the top-left corner and tries to move to the bottom-right corner. The robot can only move either down or right. Given the two integers m and n, return the number of possible unique paths.
Examples
Example 1
- Input:
- m = 3, n = 7
- Output:
- 28
Constraints
- •1 <= m, n <= 100
C++ Solution
solution.cpp
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
return helper(m, n, 1, 1, memo);
}
int helper(int m, int n, int i, int j, vector<vector<int>> &memo) {
if (i > m || j > n) return 0;
if (i == m && j == n) return 1;
if (memo[i][j] != -1) return memo[i][j];
return memo[i][j] =
helper(m, n, i + 1, j, memo) + helper(m, n, i, j + 1, memo);
}
};