用kotlin完成这个题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

以下是使用递归方式和动态规划方式两种实现方法：

1. 递归方式

fun uniquePaths(m: Int, n: Int): Int {
    if (m == 1 || n == 1) {
        return 1
    }
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
}

2. 动态规划方式

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]
}

以上两种方式都可以得到正确的答案，但是动态规划方式更加高效。

相关问题

使用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

以下是使用 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` 数组中最后一个元素的值即可，它记录的是到达右下角格子的不同路径数。