爬樓梯

題目描述：假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/climbing-stairs/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

問題解析

典型的斐波那契數(shù)列，因為到第n個臺階有2種走法， 要么是從第n-1個臺階上去，要么是從第n-2個臺階上去，所以到第n個臺階的走法總數(shù)等于第n-1個臺階的走法加上第n-2個臺階的走法。

解法一：遞歸

遞歸調(diào)用同一個方法，首先如果n為1或者2的時候直接返回n；如果n大于2的時候則遞歸調(diào)用該方法即f(n) = f(n - 1) + f(n - 2)。

解法二：迭代

首先如果n為1或者2的時候直接返回n；如果n大于2的時候，則記錄2個之前的值分別為lastOne和lastTwo，則當前的值為這2個值的和，然后更新lastOne和lastTwo的值，直到迭代到n為止。

【每日寄語】 你的好運氣藏在你的實力里，也藏在你不為人知的努力里，你越努力，就越幸運。