[LeetCode Road] Unique Paths - Solution/C++

62. Unique Paths

Question:

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?

Example:

Input: m = 3, n = 7
Output: 28

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Input: m = 7, n = 3
Output: 28

Input: m = 3, n = 3
Output: 6

Constraints:

1 <= m, n <= 100

It's guaranteed that the answer will be less than or equal to 2 * 10⁹.

Source code

Version 1

Idea:
It is a dynamic programming (DP) problem, we need to divide DP problem to subproblems.

Any node in m x n grid, the paths of each node must be obtained from node[m-1][n] + node[m][n-1]. Hence, use recursion to get the possible paths for node[m-1][n] and node[m][n] at 9-10 line.

In addtion, we need to set some conditions to avoid m/n index out of border at 4 line and there is only 1 path at begining position(m = 1 && n == 1), hence, return 1 at 5 line.

However, some of nodes have repeat calculations, like; node[2][2] is be computed twice in 3 x 3 grid. So, we need 2d array to store an unique paths of each nodes. If it was computed, an unique paths must bigger than 0, return paths directly at 7 line.

class Solution {
public:
    int uniquePaths(int m, int n) {
        if( m <= 0 || n <= 0) return 0;
        if(m == 1 && n == 1) return 1;
        
        if(st[m][n] > 0) return st[m][n];
        
        int left = uniquePaths(m - 1, n);
        int right = uniquePaths(m, n - 1);
        st[m][n] = left + right;
        return st[m][n];
        
    }
private:
    unordered_map<int, unordered_map<int, int>> st;
};