【奇技淫巧】-- 走地图的不同路径

题目：不同路径

一个机器人位于一个 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]; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

解法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];
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

解法3：一维数组（M+N）/2

很快你会发现，原先的斜线数组，其实是中心对称的。你懂得。

我饿了，吃饭去了。

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/107619305