[Python] Climbing Stairs question
在leetcode碰見了好久不見的爬樓梯問題， 上次遇到這個問題應該是在高中的數列與級數了吧...解完以後來記錄一下。 70. 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? 你正在爬一個有n個階梯的樓梯，你可以一次跨一階或一次跨兩階，要上到樓梯頂端有幾種方法？ 假設上到第五階的方法數是f(5)，上到第四階的方法數是f(4)，上到第三階的方法數是f(3)。 考慮情境： 我已經上到第五階f(5)，回頭看我的前一步，因為一次最多跨兩階，所以有可能是從第四階或第三階上來的， 如果是從第四階上來的f(4)，上來的方法就只有一種：跨一階上來。 如果是從第三階上來的f(3)，上來的方法有兩種，跨兩階到第五階，或是先跨一階到第四階，再跨一階上到第五階， 但是先跨一階到第四階這種方法，已經在上到第四階f(4)中考慮過了，排除以後，方法也只有一種， 因此要上到第五階的方法只有兩種，一種是從第四階跨一階上來，一種是從第三階跨兩階上來。 也就是f(5)=f(4)+f(3)。 同理，可以知道f(6)=f(5)+f(4)，f(4)=f(3)+f(2)，對於第n階來說，就是f(n)=f(n-1)+f(n-2)。 另外，上到第一階f(1)=1，因為只能跨一階上來，上到第二階f(2)=2，因為可以分成兩步或是一次跨上來。 python程式碼可以從f(1),f(2),...計算到f(n)，也可以從f(n),f(n-1),f(n-2),...用遞迴方式寫。 附上第一種方法的簡單程式碼。