【陪伴式刷题】Day 35｜动态规划｜62.不同路径(Unique Paths)
刷题顺序按照代码随想录建议
题目描述
英文版描述
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10(9).
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
- Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: Right -> Down -> Down Down -> Down -> Right Down -> Right -> Down
Constrains：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10^9
英文版地址
中文版描述
一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入： m = 3, n = 7 输出： 28
示例 2：
- 输入： m = 3, n = 2 输出： 3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下
示例 3：
输入： m = 7, n = 3 输出： 28
示例 4：
输入： m = 3, n = 3 输出： 6
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10^9
中文版地址
解题方法
做完这道题，我的感觉就是卡哥的动规5步曲真的绝绝子！！！
class Solution {
public int uniquePaths(int m, int n) {
// 1. 确定dp[i][j]的含义 代表到达当前行为i，列为j的格子的路径总数
int[][] dp = new int[m][n];
// 2. 初始化数组
// 3. 确定递推公式
// 4. 确定遍历顺序
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
dp[i][j] = 1;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
// 5. 输出dp数组
return dp[m - 1][n - 1];
}
}
我们直接按照动规五部曲进行解题：
- 确定dp[i][j]（因为本题有行有列，所以是二维数组）的含义
-
- 此题中代表到达当前行为i，列为j的格子的路径总数
- 确定递推公式
-
- 根据题意我们不难分析出如下规律：
-
-
- 行为i，列为j的格子只能由它左边的👈格子或者它上面的👆格子到达（因为题目规定只能向右👉或者向下👇走）因此，行为i，列为j的格子的路径总数等于行为i-1，列为j的格子的路径总数 + 行为i，列为j-1的格子的路径总数
- 即：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
-
- dp数组的初始化
-
- 由于递推公式里出现了i - 1和j - 1因此，我们需要至少初始化i = 1和j = 1以及其之前的格子的dp值
- 确定遍历顺序
这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，即前面的可以推导出后面的，因此选择从上到下、从左到到右的遍历顺序
- 输出推导dp数组（非必需～=主要用来排查问题）
复杂度分析
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)，即为存储所有状态需要的二维数组的空间