LeetCode - Medium - 62. Unique Paths

Topic

• Math
• Dynamic Programming
• Combinatorics

Description

link

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

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

Example 2:

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
1
2
3
4
5
6

Constraints:

• 1 <= m, n <= 100

Analysis

方法一：深度优先搜索（略）

方法二：动态规划（递归版与迭代版）

方法三：组合数学公式（略）

标略的参考详细解题说明-Carl的教程

Submissions

public class UniquePaths {
	
	//方法二：动态规划（递归版）
	public int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n];
		return helper(m - 1, n - 1, dp);
	}
	
	private int helper(int i, int j, int[][] dp) {
		if(dp[i][j] == 0) {
			if(i == 0 || j == 0) {
				dp[i][j] = 1;
			}else {
				dp[i][j] = helper(i - 1, j, dp) + helper(i, j - 1, dp);
			}
		}
		return dp[i][j];
	}

	//方法二：动态规划（迭代版）
	public int uniquePaths2(int m, int n) {
		int[][] dp = new int[m][n];
		
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
				}
			}
		}
		return dp[m - 1][n - 1];
	}
	
	
	//方法二：动态规划（迭代版）（优化）
	public int uniquePaths3(int m, int n) {
		int[] dp = new int[n];

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0) {
					dp[j] = 1;
				} else if (j > 0) {
					dp[j] += dp[j - 1];
				}
			}
		}

		return dp[n - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Test

import static org.junit.Assert.*;

import org.junit.Test;

public class UniquePathsTest {

	@Test
	public void testUniquePaths() {
		UniquePaths up = new UniquePaths();
		
		assertEquals(28, up.uniquePaths(3, 7));
		assertEquals(3, up.uniquePaths(3, 2));

		assertEquals(28, up.uniquePaths(3, 7));
		assertEquals(3, up.uniquePaths(3, 2));
		
		assertEquals(28, up.uniquePaths3(3, 7));
		assertEquals(3, up.uniquePaths3(3, 2));
	}

}

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