这是我参与8月更文挑战的第29天，活动详情查看：8月更文挑战

前言

力扣第六十二题 不同路径 如下所示：

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

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

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

示例 1：

输入： m = 3, n = 7
输出： 28
复制代码

示例 2：

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

示例 3：

输入： m = 7, n = 3
输出： 28
复制代码

一、思路

这一题也是一道非常经典的动态规划题目，当然也可以使用组合数学来解答。因为从左上角到右下角，所走的步数中 向右的次数 和 向下的次数 时固定的。但是在这里就不做深究了，此处仅以动态规划作为讲解，如对组合数学感兴趣，可以自行查看力扣官方题解。

不同路径这一题中有两个重要的信息：

• 每次只能向右或向下
• 需要计算的结果为不同路径的数量

所以我们可以设 dp[i][j] 为从左上角 [0][0] 到 [i][j] 点可能的数量。又因为第一行和第一列的位置只有一种走法，所以可得 dp[0][] = 1，dp[][0] = 1。

经过推理，动态规划状态转移方程如右：dp[i][j] = dp[i-1][j] + dp[i][j-1] (i>1, j>1)

接下来的事情就很简单了，遍历二维数组 dp 并填充相应的值，直到 i == m, j == 3 结束

图解动态规划

此处以 m=3, n=4 作为例子

1. 初始化二维数组 dp[3][4] 如下图所示

2. 先填充第一行和第一列，值都为 1

3. 从第二行开始遍历，当 i=1 时，根据状态转移方程填充此行

4. 当 i=2 时，根据状态转移方程填充此行

5. 返回 dp[2][3] 的结果 10 即可

二、实现

实现代码

实现代码与思路中保持一致

    /**
     * 动态规划
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 初始化第一行和第一列
        for (int i=0; i<n; i++) {
            dp[0][i] = 1;
        }
        for (int i=0; i<m; i++) {
            dp[i][0] = 1;
        }
        // 遍历dp（从 [1][1] 开始）
        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];
    }
复制代码

测试代码

    public static void main(String[] args) {
        new Number62().uniquePaths(3, 4);
    }
复制代码

结果

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~