leetcode刷题（122）——62. 不同路径

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

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

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

示例 1：

输入：m = 3, n = 7
输出：28
1
2

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
1
2
3
4
5
6
7

示例 3：

输入：m = 7, n = 3
输出：28
1
2

示例 4：

输入：m = 3, n = 3
输出：6
1
2

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

动态规划

对于(0,0)这个点来说，它只能往右走、或者往下走。
那么反过来看，哪个点可以到达(2,2)呢？

只能是它的上方(1,2)这个点
或者是它的左方(2,1)这个点

搞清楚这个关系，动态规划的转移方程就可以很容易写出来了：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
1

解决了核心逻辑，再把边界条件处理下就可以了。
递归的边界条件是走到了最右边一列、或者是走到了最下面一行。
动态规划正好是反过来的，因为我们是从上到下一行一行推导的。
所以我们要处理下第一行和第一列，将它们都赋予1即可。

时间复杂度：O(M * N)O(M∗N)
空间复杂度：O(M * N)O(M∗N)

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //第一行都赋予 1
        for(int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        //第一列都赋予 1
        for(int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }
        //两个for循环推导，对于(i,j)来说，只能由上方或者左方转移过来
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                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
15
16
17
18
19
20

动态规划+空间优化

我们在二维数组推导的时发现，dp[i][j]的值来自于dp[i - 1][j]和dp[i][j - 1]。
也就是只需要上一行的值就可以了，上上一行的并不需要了，所以这里可以用滚动数组的方式优化一下空间。

以上图所述，对于第三行10这个值，需要上方的值+左方的值。而经过上一次计算之后，第四列的值是4。
此时我们并不需要再跟上一行的做累加，只需要用4加上左边的6就可以了。
所以我们可以申请一维数组，数组长度就是n。
将原先
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
改为：
dp[j] = dp[j] + dp[j - 1]。

时间复杂度：O(M * N)O(M∗N)
空间复杂度：O(N)O(N)

class Solution {
    public int uniquePaths(int m, int n) {
        //一维空间，其大小为 n
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                //等式右边的 dp[j]是上一次计算后的，加上左边的dp[j-1]即为当前结果
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对于空间优化的补充：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]   
1

虽然用到了二维数组，但是计算第 i 行时，只需要 i - 1 行的内容就可以了
所以用一维数组来代替

那么这句就很关键:

dp[j] = dp[j] + dp[j - 1]
1

对比下 一维和二维的这两个公式，其实有相似的地方
拿等号右边来对比说：

dp[i - 1][j] + dp[i][j - 1]  
 dp[j] + dp[j - 1]
1
2

dp[j - 1]　就类似于　dp[i][j - 1] ，这是本行左边的那个值　　 dp[j] 就类似于 dp[i - 1][j] ，这里的dp[j]不是本行的，是“上一次”计算的结果　　　 这里的重点就是“上一行”计算结果，等号右边两个值相加后又赋给了dp[j]
那么下一轮再计算时， dp[j]的值就是“上一次”计算的结果了

# dp[i - 1][j] 是来自上方的，dp[i][j - 1]来自左边
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

# dp[j] 是上一次迭代计算后的当前位置，相当于二维数组中的“上方”
# dp[j - 1] 是刚刚计算后的左边，相当于二维数组中的“左边”
dp[j] = dp[j] + dp[j - 1];
1
2
3
4
5
6

二维和一维都是从左往右更新的，所以计算dp[j]时，dp[j - 1]就已经计算好了 于是拿着 上一次迭代后的当前位置 + 刚刚计算后的左边位置，加起来就是当前结果了 而这个结果会被继续使用到
可以看下题解里面的最后一张图，那个就是一行一行更新后的效果

下面的图，就是叠加后的示例结果：