Problem description:

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?

Solution:

Naive solution. Use a 2D array, initialize it with 0th row and 0th column to 1(because only one way to reach).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i= 0; i< m; i++){
            dp[i][0]= 1;
        }
        for(int i= 0; i< n; i++){
            dp[0][i]= 1;
        }
        
        for(int r= 1; r< m; r++){
            for(int c= 1; c< n; c++){
                dp[r][c]= dp[r-1][c]+ dp[r][c-1];
            }
        }
        
        return dp[m-1][n-1];
    }
};

time complexity: $O(mn)$
space complexity: $O(mn)$

Solution 2:

Optimized the space usage:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for(int r= 1; r< m; r++){
            for(int i= 1; i< n; i++){
                dp[i]+= dp[i-1];
            }
        }
        return dp[n-1];
    }
};

time complexity: $O(m*n)$
space complexity: $O(n)$

reference: