Ricky.L的随笔
0%

LeetCode.63.不同路径 II（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.63.不同路径 II（中等）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

题解

有障碍物说明不能达到，换句话说，到达障碍物格子的路径数为0。

设dp[i][j]为到达[i, j]格的路径数。

状态转移方程

  1. [i, j]没有障碍物，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
  2. [i, j]有障碍物，dp[i][j] = 0。
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
class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        val dp = Array(m) { IntArray(n) { 0 } }

        // 第一列
        for (i in 0 until m) {
            // 遇到障碍物，下面格子都不能到达，路径数为0
            if (obstacleGrid[i][0] == 1) break
            dp[i][0] = 1
        }

        // 第一行
        for (j in 0 until n) {
            // 遇到障碍物，右边格子都不能到达，路径数为0
            if (obstacleGrid[0][j] == 1) break
            dp[0][j] = 1
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (obstacleGrid[i][j] == 1) dp[i][j] = 0
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        
        return dp[m - 1][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
class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        val dp = IntArray(n) { 0 }

        // 第一行
        for (j in 0 until n) {
            // 遇到障碍物，右边格子都不能到达，路径数为0
            if (obstacleGrid[0][j] == 1) break
            dp[j] = 1
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (obstacleGrid[i][j] == 1) dp[j] = 0
                // dp[j]: 达到上方格子的路径数
                // dp[j - 1]: 达到左方格子的路径数
                else dp[j] = dp[j] + dp[j - 1]
            }
        }
        
        return dp[n - 1]
    }
}