当前位置：首页 > article >正文

leetcode hot100【LeetCode 62.不同路径】java实现

article 2024/11/19 7:42:10

LeetCode 62.不同路径

题目描述

给定一个 m x n 网格，从左上角到右下角有多少条不同的路径。机器人每次只能向下或者向右移动一步。

示例 1:

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

示例 2:

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

提示：

1 <= m, n <= 100

Java 实现代码

class Solution {
    public int uniquePaths(int m, int n) {
        // 创建一个m行n列二维数组 dp，
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 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]; // dp[i][j]表示当前位置的路径数
            }
        }
        return dp[m - 1][n - 1]; // 最终的结果就是 dp[m - 1][n - 1]
    }
}

解题思路

该问题可以使用动态规划来解决。具体思路如下：

定义状态： 设 dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的不同路径数。

状态转移：

机器人只能从上方或左方到达当前格子。因此，dp[i][j] 可以由 dp[i-1][j]（上方）和 dp[i][j-1]（左方）之和得到。
即： [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]
其中，dp[i-1][j] 表示从上方来，dp[i][j-1] 表示从左方来。

边界条件：

如果 i == 0 或 j == 0，意味着机器人只能沿着边界移动，所以这些格子的路径数为 1。
即： [ dp[i][0] = 1 and dp[0][j] = 1 ]

求解： 最终答案为 dp[m-1][n-1]，即到达右下角的不同路径数。