By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 62. Unique Paths.

Here shows 3 Approaches to slove this problem: Dynamic Programming, Recursion, Math.

Dynamic Programming

The equation is: \(f(i, j) = f(i−1, j) + f(i, j−1)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1] + 1, dp[i][j - 1] + dp[i - 1][j]);
        }
    }

    return dp[m - 1][n - 1];
}

Analysis

• Time Complexity: \(O(mn)\)
• Space Complexity: \(O(mn)\)

Recursion

The DFS is top-down dynamic programming with memoization. If we do ordinary DFS without proper memoization, it will have a TLE error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int uniquePaths(int m, int n) {
    return dfs(new HashMap<Pair, Integer>(), 0, 0, m, n);
}

private static int dfs(Map<Pair, Integer> cache, int r, int c, int rows, int cols) {
    Pair p = new Pair(r, c);

    if (cache.containsKey(p)) {
        return cache.get(p);
    }

    if (r == rows - 1 || c == cols - 1) {
        return 1;
    }
    
    cache.put(p, dfs(cache, r + 1, c, rows, cols) + dfs(cache, r, c + 1, rows, cols));
    return cache.get(p);
}

Analysis

• Time Complexity: \(O(mn)\)
• Space Complexity: \(O(mn)\)

Combination Math

In the process from the top left to the bottom right, we need to move \(m+n-2\) steps, of which there are \(m-1\) moves down and \(n-1\) times to the right.

Therefore, the total number of paths is equal to the number of options for selecting \(m-1\) downward moves from \(m+n-2\) moves, that is, the number of combinations:

\[ {\Large C}_{m+n-2}^{m-1} = \binom{m+n-2}{m-1} = \frac{(m+n-2)(m+n-3)\cdots n}{(m-1)!} = \frac{(m+n-2)!}{(m-1)!(n-1)!} \]

We can use \(\frac{(m+n-2)(m+n-3)\cdots n}{(m-1)!}\) to calcuate the number. ​

1
2
3
4
5
6
7
8
9

public static int uniquePaths_math(int m, int n) {
    long ans = 1;
    
    for (int x = n, y = 1; y < m; ++x, ++y) {
        ans = ans * x / y;
    }

    return (int) ans;
}

Analysis

• Time Complexity: \(O(m)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗