【陪伴式刷题】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:

1. 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

英文版地址

leetcode.com/problems/un…

中文版描述

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

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

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

示例 1：

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

示例 2：

1. 输入： 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

中文版地址

leetcode.cn/problems/un…

解题方法

做完这道题，我的感觉就是卡哥的动规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];
    }
}

我们直接按照动规五部曲进行解题：

1. 确定dp[i][j]（因为本题有行有列，所以是二维数组）的含义

1. 1. 此题中代表到达当前行为i，列为j的格子的路径总数

1. 确定递推公式

1. 1. 根据题意我们不难分析出如下规律：

1. 1. 1. 行为i，列为j的格子只能由它左边的👈格子或者它上面的👆格子到达（因为题目规定只能向右👉或者向下👇走）因此，行为i，列为j的格子的路径总数等于行为i-1，列为j的格子的路径总数 + 行为i，列为j-1的格子的路径总数
      2. 即：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

1. dp数组的初始化

1. 1. 由于递推公式里出现了i - 1和j - 1因此，我们需要至少初始化i = 1和j = 1以及其之前的格子的dp值

1. 确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，即前面的可以推导出后面的，因此选择从上到下、从左到到右的遍历顺序

1. 输出推导dp数组（非必需～=主要用来排查问题）

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)，即为存储所有状态需要的二维数组的空间