LeetCode:62. 不同路径
62. 不同路径
来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/unique-paths/一个机器人位于一个 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
示例 4：
输入：m = 3, n = 3
输出：6
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于
解法
- 动态规划：四个步骤：
- 问题定义
- 状态转移方程
- 初始条件和边界情况
- 确定计算顺序（自顶向下，还是自下向上）
问题定义：机器人走到最后一个格子的次数，由于机器人只能往右往下方向移动，要求最后一个格子的所有路径。如果我们知道了该格子上面的那个格子的路径总数，以及格子左边格子的路径总数，最后一个格子的路径总数等于上面那个格子以及左边那个格子的路径和，类似于斐波拉契数列
，这里可以用递归方式，可以用动态规划方式，由于递归的复杂度太高，这里用动态规划进行解决
状态转移方程：但这里是二维的，可以用一个二维数组定义该问题
初始化条件和边界条件
由于只能向右和向下移动，所以第一行都只有一种路径方式到达，第一列也是只有一种路径方式达到，所以初始化
dp[i][0] = 1 for i in range(m)dp[0][j] = 1 for j in range(n)
确定计算顺序: 这个是从下向上的方向计算即可
代码实现
动态规划
python实现
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 and n == 1:
return 1
dp = [[0] * n for _ in range(m)]
for i in range(n):
dp[0][i] = 1
for j in range(m):
dp[j][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
c++实现
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(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];
}
}
return dp[m-1][n-1];
}
};
复杂度分析
- 时间复杂度：
- 空间复杂度：
优化
dp[i][j] = dp[i-1][j] + dp[i][j-1] --> cur[j] = cur[j-1] + pre[j]由于每次更新的时候只与当前行和最上面一行有关系，我们可以将存储整个二维矩阵替换成只保存当前层和上一层，空间复杂度从
变成
python实现
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 and n == 1:
return 1
pre = [1] * n # 上一行
cur = [1] * n # 当前行
# 只需要保留当前行与上一行的数据 pre[j] = dp[i-1][j]
# 前一行当列往下走，这一行前一列往下走，更新前一行
# 两行，空间复杂度O(2n)
for i in range(1, m):
for j in range(1, n):
cur[j] = cur[j-1] + pre[j]
pre = cur[:]
return pre[-1]
c++实现
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> pre_row (n, 1);
vector<int> cur_row (n, 1);
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
cur_row[j] = cur_row[j-1] + pre_row[j];
}
pre_row = cur_row;
}
return pre_row[n-1];
}
};
复杂度分析
- 时间复杂度：
- 空间复杂度：
继续优化
我们可以将其压缩为一行， cur[j] = cur[j-1] + pre[j] -> cur[j] = cur[j] + cur[j-1]
每次都将新的结果重新设置给每一列即可，新的结果只与左边那一列有关系, 空间复杂度降低为
python实现
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
cur_row = [1] * n
for i in range(1, m):
for j in range(1, n):
cur_row[j] += cur_row[j-1]
return cur_row[-1]
c++实现
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> cur_row (n, 1);
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
cur_row[j] = cur_row[j] + cur_row[j-1];
}
}
return cur_row[n-1];
}
};
复杂度分析
- 时间复杂度：
- 空间复杂度：