阿里巴巴校招面试题目，还是不是十分确定，来问问大家

InMySin

这个估计大家都看见过的题目，但是我google搜素效果却不是很好，丫的居然没找到。。KuMa！

事情是这样的：
有一个m x n 的网格，从左下角的的顶点走向右上角的顶点，每次走都只能往上或者往右走一步，求这样的走法有多少种？ 并打印所有路径。

附件是例子， 3 x 4 的网格，从左下走到右上..

这个问题应该不会很难，但自己不是十分确定。。
目前想到是 递归，然后试图把递归用栈实现，能不能直接循环？？

zhaohongjian000

参考这个题目：
http://bbs.chinaunix.net/thread-3777508-1-1.html

思路是一样的，只是变成了两步。

更新：应该是3步，之前想错。

Ager

InMySin 发表于 2012-10-28 21:23
这个估计大家都看见过的题目，但是我google搜素效果却不是很好，丫的居然没找到。。KuMa！

事情是这样的 ...

不需要递归，用单纯的循环可以做的：

首先，我们从最简单的1x1网格开始：

1. x-x
   
2. | |
   
3. o-x

复制代码

我们约定：用“u”表示“往上走一步”，用“r”表示“往右边走一步”。

根据题意，小dot（o）“每次走都只能往上或者往右走一步”，那么，对于1x1网格，小o的走法只能有两种：

1：ur
2：ru

继续，我们以“日”字即2x1网格为例：

1. x-x
   
2. | |
   
3. x-x
   
4. | |
   
5. o-x

复制代码

很简单，小o的走法，只能有3种：

1：uur
2：uru
3：ruu

我们发现，对于mxn网格，小o的路径中，u一定出现m次、r一定出现n次。

此时，我们不再以u和r做标记，而以0与1代替之。

很显然，对于mxn网格，小o的走步次数，一定是m+n次。

那么，我们构造一个序列（构造序列的技巧是：将整数0 -> 整数2^(m+n)-1分别用位向量表示）：

1. 000....000（有m+n位，下同）
   
2. 000....001
   
3. 000....010
   
4. 000....011
   
5. 000.......
   
6. 111....110
   
7. 111....111

复制代码

这个序列中的每一项，都是m+n位数的。

所以，完整的序列，一定有2^(m+n)项，而这么多项中，有许多项，是不符合题意的，我们怎么把它们剔除掉呢？

很简单，上面我们已经认识到：小o的路径中，u一定出现m次、r一定出现n次，即0一定出现m次、1一定出现n次。

0一定出现m次、1一定出现n次 —— 这意味着：将序列中的每一项里的位按权1累加起来，如果和==n，（24楼有超级简便方法）即是符合题意的路径。

解毕。

KanonInD

回复 1# InMySin
如果想偷懒的话，求二项式系数就行了。

   

linux_c_py_php

动态规划肯定是可以的.

Ager

linux_c_py_php 发表于 2012-10-28 22:47
动态规划肯定是可以的.

龙哥来刷版了，用的是24K金粉！！！！

linux_c_py_php

{:3_184:}

Ager 发表于 2012-10-28 23:04
龙哥来刷版了，用的是24K金粉！！！！

Ager

linux_c_py_php 发表于 2012-10-28 23:06
{:3_184:}

cjaizss

C(m+n,n)