Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
提示 | 解題應用 |
---|---|
DynamicProgramming | 規律觀察 |
Default:
|
|
解答思路:
也許是解題的敏感度不足,看到此題便很快速的想要用排序組合的方式來運算,好比說4個階梯有2個1步與2個2步的不同走法數就是4!/(2!2!),在排序組合就是總數!(階)去除上兩個彼此相異數!的乘積,如此一來其它狀況也藉由此方式來算最後總合起來就是結果,聽起來合情合理,可是電腦要算的話光是35階這個數或更小就足以讓你溢位了,所以看來不是以這種方式來解決問題,而最後從整體數序來觀察規律就可以很輕易的將此題給搞定了,1, 2, 3, 5, 8…,其實就是很標準的費式數列: *第三項值 = 第一項值 + 第二項值
程式碼解說:
因為相當單純,就直接用迴圈來做就不使用遞回的方式了,因為費式數列至少需要開頭兩項的值,1階當然只有一種走法,而2階則兩種走法,其餘的階梯算法就只要先把總階數減2(第1,第二階)再不斷用迴圈計算第三項,並暫存前兩項的值即可
|
|
完整程式碼:
|
|
總結:
算階梯走法不是考數學,所以不需要會排序組合,要的只是對數列做觀查,從而發現其為費式數列。