一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径?
时间: 2023-03-29 07:04:03 浏览: 62
这是一个经典的组合问题,可以使用组合数学的方法来解决。机器人需要向右移动 n-1 次,向下移动 m-1 次,总共需要移动 n-1+m-1=n+m-2 次。因此,不同的路径数就是从 n+m-2 个元素中选择 n-1 个元素的组合数,即 C(n+m-2, n-1)。
相关问题
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“start” )。 机
器人每次只能向下或者向右移动一格,直到到达右下角的终点(下图中标记为“end”)。现在给定了一些障碍物用 1 来表示,机器人不能通过。请问机器人能否到达终点?
这是一道动态规划问题。我们可以定义一个二维数组 dp,其中 dp[i][j] 表示机器人到达(i, j)这个位置是否可行(1 表示可行,0 表示不可行)。那么我们需要先初始化 dp 数组:
- 如果起点 (0, 0) 有障碍物,dp[0][0] = 0;
- 否则,dp[0][0] = 1;
- 对于第一行和第一列,如果前一个格子可行并且当前格子没有障碍物,那么当前格子也可行,即 dp[0][j] = dp[0][j-1] && obstacleGrid[0][j] = 0,dp[i][0] = dp[i-1][0] && obstacleGrid[i][0] = 0;
- 对于其他格子 (i, j),如果当前格子没有障碍物,那么机器人到达当前格子的路径有两种可能:从上面的格子到达或者从左边的格子到达。即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
最终,dp[m-1][n-1] 就表示了机器人能否到达终点。如果 dp[m-1][n-1] 为 1,那么可以到达终点;否则不能到达。
用kotlin完成这个题目:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径?
以下是使用递归方式和动态规划方式两种实现方法:
1. 递归方式
```kotlin
fun uniquePaths(m: Int, n: Int): Int {
if (m == 1 || n == 1) {
return 1
}
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
}
```
2. 动态规划方式
```kotlin
fun uniquePaths(m: Int, n: Int): Int {
val dp = Array(m) { IntArray(n) }
// 初始化第一行和第一列的值为1,因为只能向右或向下移动
for (i in 0 until m) {
dp[i][0] = 1
}
for (j in 0 until n) {
dp[0][j] = 1
}
// 计算每个格子的值
for (i in 1 until m) {
for (j in 1 until n) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
// 返回右下角格子的值
return dp[m - 1][n - 1]
}
```
以上两种方式都可以得到正确的答案,但是动态规划方式更加高效。