算法---不同路径(Kotlin)

题目

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

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

问总共有多少条不同的路径？

示例 ：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

解决方法

    fun uniquePaths(m: Int, n: Int): Int {
        val dp = Array(m) { Array(n) { 0 } }
        dp[0][0] = 1
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (i == 0 && j ==0) continue
                val left = if (i - 1 >= 0) dp[i - 1][j] else 0
                val top = if (j - 1 >= 0) dp[i][j - 1] else 0
                dp[i][j] = left + top
                println(" $i $j ${dp[i][j]}")
            }
        }
        return dp[m - 1][n - 1]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

1.别人眼中最简单的，到我这里一直没有思路。看了题解才知道思路是什么。