【奇技淫巧】-- 走地图的不同路径
题目：不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
在这里插入图片描述
思路
这题其实就是爬楼梯问题的二维抽象罢了，很简单。又一次证明递归会超时。
把图画出来会发现就是个杨辉三角，问题就在于：你是要开数组，还是不开数组？要是开数组，开多大？
解法1：二维数组
用杨辉三角的办法，开一个二维数组，把每个空都填上。
代码1：
int uniquePaths(int m, int n) {
// DP with 2 dimensions array
int a[m][n];
for (int i = 0; i < m; i++) {
a[i][0] = 1;
}
for (int i = 0; i < n; i++) {
a[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
return a[m-1][n-1];
}解法2：一维数组（M+N）
把地图想象成一个正方形的地图，如果我们需要求坐标（m,n）处的值，其实前面那些只是铺垫，并没有留下的必要。 比方说我们现在要（4,5）的值，那么我们最终只需要从反斜线（0,8）->（8,0）这条线上找到（4,5），所以我们以斜线的方式前进，每次刷新的时候，就当数组的原住民不存在了，它们只需要提供一个数值。
语言是无力的，看代码
代码2：
int uniquePaths(int m, int n) {
int k = m + n - 1;
vector<int> a(k, 0);
if (k == 1)
return 1;
a[0] = 1;
a[1] = 1;
int count = 2;
while (k > 2) {
for (int i =count-1; i >0; i--) {
a[i] = a[i] + a[i - 1];
a[count] = 1;
}
count++;
k--;
}
return a[n-1];
}解法3：一维数组（M+N）/2
很快你会发现，原先的斜线数组，其实是中心对称的。你懂得。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录