d887-1-山脈種類(chain) 北市賽 99

輸入說明 ：

每行有1個數字N(2<=N<=25)

輸出說明 ：

請輸出一個整數，表示總步數為2N的山脈共有多少種。

範例輸入 ：

3

4

範例輸出 ：

5

14

提示 ：

(1)測資有誤請告知感謝

(2)另外兩題本人都只過了局部測資

請會的人幫忙出吧

出處 ：

99北市賽 (管理：leopan0922)

解題策略

分成多種情形相加

x=0到2n，才到y=0，這樣的有mt[n-1]種

x=0到2n-2，x=2n-2到y=0，這樣有mt[n-2]*mt[1]種

x=0到2n-4，x=2n-4到y=0，這樣有mt[n-3]*mt[2]種

x=0到2n-6，x=2n-6到y=0，這樣有mt[n-4]*mt[3]種

...

x=0到2，x=2到y=0，這樣有mt[n-1]種

mt[n]=mt[n-1]+mt[n-2]*mt[1]+mt[n-3]*mt[2]+mt[n-4]*mt[3]+...+mt[1]*mt[n-2]+mt[n-1]