LeetCode - Medium - 63. Unique Paths II

Topic

• Array
• Dynamic Programming
• Matrix

Description

link

You are given an m x n integer array grid. There is a robot 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.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

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

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
1
2
3
4
5
6

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
1
2

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Analysis

方法一：动态规划（二维数组）（Carl教程）

方法二：动态规划（一维数组）（我写的）

Submissions

public class UniquePathsII {
	
	//方法一：动态规划（二维数组）
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length, n = obstacleGrid[0].length;
		int[][] dp = new int[m][n];
		
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        	dp[i][0] = 1;
        }
        
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) { 
        	dp[0][j] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) 
                	continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
		return dp[m - 1][n - 1];
	}
	
	//方法二：动态规划（一维数组）
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        
        int[] dp = new int[n]; 
        int firstRowBlockIndex = n, firstColBlockIndex = m;
        for(int i = 0; i < m; i++) {
        	for(int j = 0; j < n; j++) {
        		if(obstacleGrid[i][j] == 1) {
        			if(i == 0 && firstRowBlockIndex == n) {        				
        				firstRowBlockIndex = j;
        			}
        			if(j == 0 && firstColBlockIndex == m) {
        				firstColBlockIndex = i;
        			}
        			dp[j] = 0;
        			continue;
        		} 
        		
        		if(i == 0 || j == 0) {
        			dp[j] = (i == 0 && j >= firstRowBlockIndex ||
        					j == 0 && i >= firstColBlockIndex) ? 0 : 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
54
55
56
57
58

Test

import static org.junit.Assert.*;
import org.junit.Test;

public class UniquePathsIITest {

    @Test
    public void test() {
        UniquePathsII uObj = new UniquePathsII();

        assertEquals(2, uObj.uniquePathsWithObstacles(new int[][] {{0,0,0},{0,1,0},{0,0,0}}));
        assertEquals(1, uObj.uniquePathsWithObstacles(new int[][] {{0,1},{0,0}}));
        
        assertEquals(2, uObj.uniquePathsWithObstacles2(new int[][] {{0,0,0},{0,1,0},{0,0,0}}));
        assertEquals(1, uObj.uniquePathsWithObstacles2(new int[][] {{0,1},{0,0}}));
    }
}

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