Ricky.L的随笔
0%

LeetCode.62.不同路径（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.62.不同路径（中等）

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

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

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

题解

要达到右下角[m, n]，只有两种可能：

  1. 从上边[m - 1, n]来
  2. 从左边[m, n - 1]来

[m - 1, n]怎么达到？
按道理有3条路径，从上来、从左来、从下来。
但是从下来不考虑，因为整个路径是要从上到下的，从下面上来，最后还是要下去，多此一举。

同理中间的格子，如果是从右边过来也是多此一举，因为整个路径是要从左到右的。

所以对于每个格子，只考虑从上和从左过来。

某个状态的问题就拆解为了子问题+有限步骤，并且符合最优子结构，也无后效性。
而且有大量重叠子问题，比如到达[i, j]格的路径数，在计算到达[i + 1][j]路径数和到达[i][j + 1]路径数时都会用到。

符合使用动态规划所有条件。

状态转移方程
设dp[i][j]为达到方格[i, j]的路径数。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

边界处理
[0, 0]格没有左边和上面，达到的路径数量就是1。
第一行所有格子没有上面，都只能从左边过来，路径数都是1。
第一列所有格子没有左边，都只能从上边过来，路径数都是1。

复杂度
需要查看所有格子的情况来寻找路径数，所以要遍历所有网格，时间无法省略。
时间复杂度$O(mn)$。

记录所有达到所有格子的路径数，空间复杂度$O(mn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val dp = Array(m) { IntArray(n) { 0 } }
        dp[0][0] = 1
        for (j in 1 until n) dp[0][j] = 1
        for (i in 1 until m) dp[i][0] = 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]
    }
}

空间优化

由于每个格子的路径数只会从上面和左边的路径数推导而来，而且只会读取上面和左边的项，所以不需要记录所有格子的路径数。

那么要记录多少个格子的路径数？
因为终点格子可以从左边过来，所以要记录左边所有的格子的路径数，所以记录一行是必须的。
读取上一行格子的路径数，直接读取之前记录的行就行了。
所以只需要记录一行格子的路径数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        // 存储一行格子的路径数
        val dp = IntArray(n) { 1 }
        for (i in 1 until m) {
            for (j in 1 until n) {
                // dp[j]是上面格子的路径数
                // dp[j - 1]是左边格子的路径数
                dp[j] = dp[j] + dp[j - 1]
            }
        }
        return dp[n - 1]
    }
}

时间复杂度$O(mn)$
空间复杂度$O(n)$

如果m < n，也可以做到$O(m)$空间复杂度，交换行列把矩阵转置，并不影响结果，再递推就行。