排列組合?遞迴式?

這是前幾天同學問我的
有個樓梯有七格
一次可以走一格~三格
總共可以有幾種走法

這個題目乍看下是x+2y+3z=7
先把所有解列出來 (從z開始代入比較快)
然後最後用排列組合去算

(1,0,2),(0,2,1),(2,1,1),(4,0,1),(1,3,0),(3,2,0),(5,1,0),(7,0,0)

3!/2! + 3!/2! + 4!/2! + 5!/4! + 4!/3! +5!/(3!2!)  + 6!/5! + 7!/7! =
3 + 3 + 12 + 5 +  4 + 10 + 6 + 1
= 44

但解答其實類似費式數列,遞迴式之類的
要走第七格,那上一格一定是四~六格
以第四格來說 上一格一定是從第一格到第三格

所以要先從最底部開始做 第一格沒什麼疑問 1種走法
第二格也沒什麼疑問 1+1 or 2
第三格就比較複雜 1+1+1 | 2+1 | 1+2 | 3

最苦的部分就做完了 接著就往上疊吧XD

1 2 4 7 13 24 44
1 2 3 4  5    6   7

至於哪個比較厲害,比較高手
乍看之下後者好像真的比較厲害
雖然真的比較厲害XDD

但用不同的想法去看待題目我覺得才真正訓練思維的方式吧
以前高中老師也是這樣教我們的