62.不同路径

力扣题目链接(opens new window)

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

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

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

示例 1：

• 输入：m = 3, n = 7
• 输出：28

示例 2：

• 输入：m = 2, n = 3
• 输出：3

解释： 从左上角开始，总共有 3 条路径可以到达右下角。

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

示例 3：

• 输入：m = 7, n = 3
• 输出：28

示例 4：

• 输入：m = 3, n = 3
• 输出：6

提示：

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

解题思路：

这道题的思路是使用动态规划来解决。我们可以从起点开始，逐步计算到达每个位置的不同路径数，并将结果存储在一个二维数组中。

具体步骤如下：

1. 创建一个大小为m x n的二维数组dp，用于存储到达每个位置的不同路径数。
2. 对于第一行和第一列的位置，由于只能向右或向下移动，到达这些位置的路径数都为1，所以将dp[i][0]和dp[0][j]都设置为1。
3. 使用双重循环遍历除第一行和第一列之外的其他位置(i, j)，从上方格子和左方格子的路径数之和计算出当前位置的路径数，并将结果存储在dp[i][j]中。
4. 最后返回dp[m-1][n-1]，即到达右下角的不同路径数。

代码实现：

/**
 * 62. 不同路径
 */
public class UniquePaths {
    public int uniquePaths(int m, int n) {
        if(m == 0 || n == 0){
            return 0;
        }
        int[][] dp = new int[m][n];
        //初始化：第一行和第一列都为1
        for(int i = 0; i < m ; i ++){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i ++){
            dp[0][i] = 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];
    }
}

最后，我们来举一个具体的例子来说明这道题的代码实现步骤。

假设有一个二维网格，大小为3x3，我们需要计算从左上角到右下角的不同路径数。

1. 创建一个大小为3x3的二维数组dp，用于存储路径数。

   dp = [[0, 0, 0],
         [0, 0, 0],
         [0, 0, 0]]
   ```
   
   

2. 初始化第一行和第一列的路径数为1，因为只能向右或向下移动。

   dp = [[1, 1, 1],
         [1, 0, 0],
         [1, 0, 0]]
   ```
   
   

3. 计算其他位置的路径数。从第二行、第二列开始，

   根据动态规划的转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1] 来更新路径数。

   • 计算 dp[1][1]：dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
   • 计算 dp[1][2]：dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
   • 计算 dp[2][1]：dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
   • 计算 dp[2][2]：dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

   更新后的二维数组为：

   dp = [[1, 1, 1],
         [1, 2, 3],
         [1, 3, 6]]
   ```
   
   

4. 返回 dp[2][2]，即到达右下角的不同路径数为6。

这就是使用动态规划方法解决这道题的步骤。根据不同的网格大小，可以按照相同的逻辑进行计算和更新。