阿里巴巴校招面試題目，還是不是十分確定，來問問大家

InMySin

這個估計大家都看見過的題目，但是我google搜素效果卻不是很好，丫的居然沒找到。。KuMa！

事情是這樣的：
有一個m x n 的網(wǎng)格，從左下角的的頂點走向右上角的頂點，每次走都只能往上或者往右走一步，求這樣的走法有多少種？ 并打印所有路徑。

附件是例子， 3 x 4 的網(wǎng)格，從左下走到右上..

這個問題應該不會很難，但自己不是十分確定。。
目前想到是 遞歸，然后試圖把遞歸用棧實現(xiàn)，能不能直接循環(huán)？？

zhaohongjian000

參考這個題目：
http://72891.cn/thread-3777508-1-1.html

思路是一樣的，只是變成了兩步。

更新：應該是3步，之前想錯。

Ager

InMySin 發(fā)表于 2012-10-28 21:23
這個估計大家都看見過的題目，但是我google搜素效果卻不是很好，丫的居然沒找到。。KuMa！

事情是這樣的 ...

不需要遞歸，用單純的循環(huán)可以做的：

首先，我們從最簡單的1x1網(wǎng)格開始：

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

復制代碼

我們約定：用“u”表示“往上走一步”，用“r”表示“往右邊走一步”。

根據(jù)題意，小dot（o）“每次走都只能往上或者往右走一步”，那么，對于1x1網(wǎng)格，小o的走法只能有兩種：

1：ur
2：ru

繼續(xù)，我們以“日”字即2x1網(wǎng)格為例：

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

復制代碼

很簡單，小o的走法，只能有3種：

1：uur
2：uru
3：ruu

我們發(fā)現(xiàn)，對于mxn網(wǎng)格，小o的路徑中，u一定出現(xiàn)m次、r一定出現(xiàn)n次。

此時，我們不再以u和r做標記，而以0與1代替之。

很顯然，對于mxn網(wǎng)格，小o的走步次數(shù)，一定是m+n次。

那么，我們構造一個序列（構造序列的技巧是：將整數(shù)0 -> 整數(shù)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位數(shù)的。

所以，完整的序列，一定有2^(m+n)項，而這么多項中，有許多項，是不符合題意的，我們怎么把它們剔除掉呢？

很簡單，上面我們已經(jīng)認識到：小o的路徑中，u一定出現(xiàn)m次、r一定出現(xiàn)n次，即0一定出現(xiàn)m次、1一定出現(xiàn)n次。

0一定出現(xiàn)m次、1一定出現(xiàn)n次 —— 這意味著：將序列中的每一項里的位按權1累加起來，如果和==n，（24樓有超級簡便方法）即是符合題意的路徑。

解畢。

KanonInD

回復 1# InMySin
如果想偷懶的話，求二項式系數(shù)就行了。

   

linux_c_py_php

動態(tài)規(guī)劃肯定是可以的.

Ager

linux_c_py_php 發(fā)表于 2012-10-28 22:47
動態(tài)規(guī)劃肯定是可以的.

龍哥來刷版了，用的是24K金粉�。。�！

linux_c_py_php

{:3_184:}

Ager 發(fā)表于 2012-10-28 23:04
龍哥來刷版了，用的是24K金粉�。。�！

Ager

linux_c_py_php 發(fā)表于 2012-10-28 23:06
{:3_184:}

cjaizss

C(m+n,n)