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

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(i1,j)+f(i,j1)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+n2m+n-2 steps, of which there are m1m-1 moves down and n1n-1 times to the right.

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

Cm+n2m1=(m+n2m1)=(m+n2)(m+n3)n(m1)!=(m+n2)!(m1)!(n1)!{\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+n2)(m+n3)n(m1)!\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. 😉😃💗