前幾個星期的面試題都有點稀奇古怪，這個星期來一個正常點的題目，可是這題目可能對於個別人來說是如此的熟悉但又很陌生。因為那是我們高中時常做的題目，現在卻還給老師了。那讓我們好好回憶一下。
6× 9的的方格中，起點的左下角，終點在右上角，從起點到終點，只能從下向上，從左向右走，問一共有多少種不同的走法。
A. 4200
B. 5005
C. 1005
D. 以上都不正確
當然這道題有點異議，為什麼這樣說呢？因為題目沒有明確說明是按方格來走還是按照線來走。
首先我們嘗試下按方格來走，得到的結果是什麼？要想知道結果，我們需要知道題目想考察我們什麼，很顯然，題目其實考察我們高中非常熟悉的排列組合的問題，完完全全就是高中的題目，可是現在可能對於我們來說又是如此的陌生。這道題如果按方格來走的話，結果就是 C(5, 13) = 1287 。13 是哪裡來的，5 又是哪裡來的，思考之前，我們可以先看一張圖。
根據圖片可以看出，13 就從左下角到右上角一個要走的格子數，5 就是走的行數，為什麼是從 13 個中選 5 個來組合就知道一共有多少種走法呢？其實因為我們只要知道了行數的 5 個的位置我們就知道列數 8 個格子的位置，當然你也可以 13 選 8 ，結果都是一樣的。為啥一樣，貼一張圖來回憶起我們遺忘的記憶吧。
因此，按走的是格子來算，結果是 C(5, 13) = C(8, 13) = 1287
其實這道題目想表達的意思是按線來算的，可是原理還是跟上面一樣的
因此，按走的是線來算，結果是 C(6, 15) = C(9, 15) = 5005
其實這種題目很多大企業大公司都會作為面試題，比如我們來看看下面兩道類似的題目：
1.阿裡巴巴的筆試題目
說 16 個人按順序去買燒餅，其中 8 個人每人身上只有一張 5 塊錢，另外 8 個人每人身上只有一張 10 塊錢。燒餅 5 塊一個，開始時燒餅店老板身上沒有錢。16 個顧客互相不通氣，每人只買一個。問這 16 個人共有多少種排列方法能避免找不開錢的情況出現。
假設付 5 塊錢的人都是 1，付 10 塊錢的人都是 0 ，則排隊順序可能為1111111100000000 或各種 1 與 0 的排列組合，那麼總共的排列順序就是C（16，8），這裡跟上面的都是一樣的，但是為了避免找不開錢，則從左到右時，不能有 0 的數目小於 1 的數目的情況出現。如果出現這種情況，則必然存在第2m+1 個數目時（即某個奇數數目），前 2m+1 個數目中有 m+1個0，m 個 1 。那麼在剩余的 16-2m-1 個數目中，即 15-2m 個數目中，必然存在著 8-m-1 個 0 ，8-m 個 1 ，即 7-m 個 0 ，8-m 個 1 。現在再把剩余的 16-2m-1 個數目中的 0 與 1 互換，則為 8-m 個0，7-m 個 1 ，這個時候，整個數列就變為了 9 個 0，7 個 1 。所以一個不符合要求的數目為 9 個 0 和 7 個 1 組成。因此，結果為 C（16，8）-C（16，9）= 12870 - 11440 = 1430
2.2012騰訊實習招聘筆試題
在圖書館一共6個人在排隊，3個還《面試寶典》一書，3個在借《面試寶典》一書，圖書館此時沒有了面試寶典了，求他們排隊的總數？
其實這些問題可以轉化為下面的格路問題，從左下角到右上角，不能是對角線，有多少種方案。不過加了限制條件而已，這道題跟阿裡巴巴那道面試題一樣，結果為：結果為 C（6，3）-C（6，4）= 20 - 15 = 5
GitHub:https://github.com/TwoWater/Interview/tree/master/Interview
package com.liangdianshui;
/**
* <p>
* 6× 9的的方格中，起點的左下角，終點在右上角，從起點到終點，只能從下向上，從左向右走，問一共有多少種不同的走法。
* A. 4200
* B. 5005
* C. 1005
* D. 以上都不正確
* </p>
*
* @author liangdianshui
*
*/
public class Catalan {
public static void main(String[] args) {
System.out.println(func(6, 9));
}
public static int func(int m, int n) {
if (m < 1 || n < 1) {
return 1;
}
return func(m - 1, n) + func(m, n - 1);
}
}
