LeetCode 62 Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
DifficultyMedium
Related Problems
[LeetCode 63] Unique Paths II Medium
[LeetCode 64] Minimum Path Sum Medium
[LeetCode 174] Dungeon Game Hard
Analysis:
This is a classic problem that can be solved by applying dynamic programming idea.
Idea 1
2d Dynamic Programming
Time: O(m^n)
Space: O(m*n)
Use dp[i][j] to represent the total number of path from (0, 0) to (i, j).
Transition function is DP[i][j] = DP[i-1][j] + DP[i][j-1], since each value comes from the left and up grid.
- Since the robot can only move toward right or bottom, the value of
dp[i][j]is the union of thedp[i-1][j]anddp[i][j-1]therefore, the transition formula is:dp[i][j] = dp[i-1][j] + dp[i][j-1]. - The initial states/values.
For grids on top line or leftmost line, we can only reach them from original location (0, 0) by straight way (horizontal or vertical),
by which means there is only one path to each grid in top line or leftmost line. Therefore,
dp[0][j] = dp[i][0] = 1, alsodp[0][0] = 1.
Idea 2
Dynamic programming using Rolling array to reduce space complexity
Time: O(m^n)
Space: O(n)
When we process the grid line by line from top to bottom, we can use dp[j] to represent each grid's value in the line i.
In another word, we use dp[j] represent dp[i][j], and dp[j-1] represents dp[i][j-1] in the previous solution.
Use a 1-d array to replace the 2-d array. use this 1-d array to iterate down the 2-d matrix line by line, each element in the 1-d array will be updated since it remembers the previous value when we are iterating down.
Note that dp[j] can have different meaning in different dp problems.
For example, in here, since we are calculating the unique path, it means the number of unique path from the first point (i, 0) of each line to its forwarding point (i, j), which is all 1s. In other cases if we are asked to calculate the min distance of path, it can mean the distance of visited path.
Idea 3
DFS, will TLE.
Idea 4
DFS, bottom up with memoir
Inital condition:
map[0][i] = 1; 0 <= i < n
map[i][0] = 1; 0 <= i < m
map[i][j] = 0; others i, j
We record the value of each visited position
Solutions
- DP with 2D Array
class Solution {
public:
int uniquePaths(int m, int n){
vector<vector<int>> dp(m, vector<int>(n, 1)); // initialize dp[0][0] = dp[0][j] = dp[i][0] = 1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
- DP with 1D Array
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> maxpath(n, 0);
maxpath[0] = 1;
for(int i = 0; i< m; i++){
for(int j = 1; j < n; j++){
maxpath[j] += maxpath[j - 1]
}
}
return maxpath[n - 1];
}
};
- DFS
class Solution {
public:
int uniquePaths(int m, int n) {
if(m == 0 || n == 0) return 1;
return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}
};
- DFS with memoir from bottom up
class Solution {
public:
int uniquePaths(int m, int n) {
this->mm = vector<vector<int>>(m, vector<int>(n, 0));
return dfs(m-1, n-1);
}
private:
vector<vector<int>> mm;
int dfs(int m, int n) {
if(m == 0 || n == 0) return 1;
return getOrUpdate(m-1, n) + getOrUpdate(m, n-1);
}
int getOrUpdate(int m,int n) {
if(mm[m][n] != 0) return mm[m][n];
else
return mm[m][n] = dfs(m,n);
}
};
- Golang solution
func uniquePaths(m int, n int) int {
dp := make([]int, n)
dp[0] = 1
for i := 0; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] += dp[j-1]
}
}
return dp[n-1]
}