使用kotlin完成这个题目:63. 不同路径 II 提示 中等 1.1K 相关企业 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径? 网格中的障碍物和空位置分别用 1 和 0 来表示。 示例 1: 输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出:2 解释:3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径: 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 示例 2: 输入:obstacleGrid = [[0,1],[0,0]] 输出:1 提示: m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
时间: 2024-02-25 18:52:05 浏览: 18
以下是使用 Kotlin 解决这个问题的代码:
```kotlin
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
val m = obstacleGrid.size
val n = obstacleGrid[0].size
val dp = IntArray(n)
dp[0] = if (obstacleGrid[0][0] == 0) 1 else 0
for (i in 0 until m) {
for (j in 0 until n) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0
} else if (j > 0) {
dp[j] += dp[j - 1]
}
}
}
return dp[n - 1]
}
```
这个算法的核心思想是使用动态规划,用一个一维数组 `dp` 来记录到达每一个格子的不同路径数。由于每次只能向下或向右移动一步,因此到达一个格子的路径数只能从它的上面或左边的格子转移而来。如果某个格子上有障碍物,则不能到达,路径数为 0。
具体地,我们可以使用一个一维数组 `dp` 来记录到达每一列的格子的路径数。对于第一行的格子,如果该格子上有障碍物,则它右边的格子都无法到达,路径数为 0;否则,它右边的格子只能从它自己转移而来,路径数为 1。对于其他行的格子,如果该格子上有障碍物,则它本身的路径数为 0;否则,它的路径数等于从它上面的格子转移来的路径数和从它左边的格子转移来的路径数之和。
最终,我们只需要返回 `dp` 数组中最后一个元素的值即可,它记录的是到达右下角格子的不同路径数。