0%

LeetCode-62-不同路径

LeetCode 62 不同路径

62.不同路径

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

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

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

LeetCode_62_不同路径

动态规划

  1. 确定动态规划数组的含义:定义二维动态规划数组 dp[i][j] 表示到达途中 i,j 位置处存在几条路径

  2. 确定递推关系:由于在题中规定只能向下和向右移动,那么对于位置 i,j 存在着两中到达的方式,第一种是从上方 i-1,j 向下一步,第二种是从左边 i,j-1 向右一步到达。那么 dp[i][j]=dp[i-1][j]+dp[i][j-1]

  3. 动态规划数组的初始化:首先是 dp[0][0] 也就是起点,那么只有一条路径,初始化为 dp[0][0]=1 ,对于 dp[i][0] 也就是最左边一列的元素,只能从起点处不断向下走 dp[i][0]=1 ,同理最上方一行 dp[0][i]=1

  4. 遍历方式:采取逐行或者逐列遍历的方式都是可行的。

  5. 举例说明: m = 3, n = 2 ,首先完成初始化:dp[0][0]=0,dp[1][0]=1,dp[2][0]=1,dp[0][1]=1 再基础上逐行进行推导:第2行 dp[1][1]=dp[0][1]+dp[1][0]=2 在此基础上推导第三行: dp[2][1]=dp[1][1]+dp[2][0]=3 验证正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp;
dp.resize(m,vector<int>(n));
// 初始化第一行和第一列
for(int i=0;i<n;i++)
dp[0][i]=1;
for(int i=0;i<m;i++)
dp[i][0]=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[n] 全部初始化为1,也就是对应这原本动态规划数组的第一列,那么在次基础上即可按行进行计算:第二行的第一个值 dp[1][0] ,此处的第二维为0,值一定为1,不需要进行计算。第二行的第二值 dp[1][1]=dp[0][1]+dp[1][0] 转化到一维数组就是 dp[1]=dp[1]+dp[0] 计算第二行的第三个数值: dp[1][2]=dp[0][2]+dp[1][1] 此处的 dp[1][1] 已经计算出了,并且 dp[0][2] 就是 dp[2] ,那么就是 dp[2]=dp[2]+dp[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n);
for (int i = 0; i < n; i++) dp[i] = 1;
for (int j = 1; j < m; j++) {
for (int i = 1; i < n; i++) {
dp[i] += dp[i - 1];
}
}
return dp[n - 1];
}
};

通过使用滚动数组的方式将空间复杂度削减到

组合数学求解

从出发点 [0,0] 走到终点 [m-1,n-1] ,至少需要向下走 m-1 步,向右走 n-1 步,总结需要 m+n-2 步,那么求解总共有多少中走法,就将问题转化为了:在 m+n-2 步中选取 m-1 步作为向下走的步数,剩余的 n-1 步自然就作为向右走的步数,那么对应路径数就为:

那么要实现 的求解,只需要使用一个for循环即可,并且对应的空间复杂度为

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int uniquePaths(int m, int n) {
long long res=1;
for(int i=n,j=1;j<m;i++,j++){
res=res*i/j;
}
return res;
}
};

关于计算过程中的整除问题:

第一次(53 / 1)任何数都可整除1

第二次(53*52 / 1*2)连续的2个数中一定有一个是2的倍数

第三次(53*52*51 / 1*2*3)连续的3个数中一定有一个是3的倍数

以此类推,每次都可以整除

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道