电视台网站模版,怎样辨别自己网站的好坏,做企业网站一般要多少钱,网站建设的简历范文62. 不同路径 - 力扣#xff08;LeetCode#xff09;
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish” #xf…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) {vectorvectorint dp(m,vectorint(n,0));for(int i0;im;i) dp[i][0] 1;for(int j0;jn;j) dp[0][j] 1;for(int i1;im;i) {for(int j1;jn;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) {vectorint 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) 动态规划中如何初始化很重要| LeetCode62.不同路径_哔哩哔哩_bilibili
