62. 不同路径 - 力扣(LeetCode)
一个机器人位于一个 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
>>动态规划
机器人从(0,0)位置出发,到(m-1,n-1)终点
按照动规五部曲分析:
1.确定dp数组(dp table)以及下标的含义
dp[i][j] : 表示 从(0,0)出发,到(i,j)有 dp[i][j]条不同的路径
2.确定递推公式
由于机器人每次只能向下或者向右移动一步。所以想要求出dp[i][j],只能从两个方向推导出来,即
dp[i-1][j] 和 dp[i][j-1],也就是说 dp[i][j] = dp[i-1][j] + dp[i][j-1];
3.dp数组的初始化
dp[i][0]一定都是1,因为从(0,0)的位置到(i,0)的路径只有一条;
dp[0][j]一定也都是1,因为从(0,0)的位置到(0,j)的路径只有一条
初始化代码为:
for(int i = 0,i < m;i++) dp[i][0] = 1;
for(int j = 0;j < n;j++) dp[0][j] = 1;
4.确定遍历顺序
dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导出来,那么从左到右一层一层遍历就可以了。可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的
5.举例推导dp数组
class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(m x n)int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));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];}
};
- 时间复杂度:O(m * n)
- 空间复杂度:O(m * n)
其实用一个一维数组(也可以理解是滚动数组)也可以,只是不利于理解,但可以优化空间,建议先理解了二维,再理解一维
class Solution {
public:// 动态规划 时间复杂度:O(m x n) 空间复杂度:O(n)int uniquePaths(int m,int n) {vector<int> dp(n);for(int j = 0;j < n;j++) dp[j] = 1;for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {dp[j] += dp[j-1];}}return dp[n-1];}
};
- 时间复杂度:O(m * n)
- 空间复杂度:O(n)
来自代码随想录的课堂截图
参考和推荐文章、视频:
代码随想录 (programmercarl.com)
动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili