[LeetCode][62. Unique Paths] 3 Approaches: Dynamic Programming, Recursion, Math

发表于 更新于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

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)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)O(mn)
  • Space Complexity: O(mn)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)O(mn)
  • Space Complexity: O(mn)O(mn)

Combination Math

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

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

Cm+n−2m−1=(m+n−2m−1)=(m+n−2)(m+n−3)⋯n(m−1)!=(m+n−2)!(m−1)!(n−1)!{\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 (m+n−2)(m+n−3)⋯n(m−1)!\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)O(m)
  • Space Complexity: O(1)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. 😉😃💗