題目

假設(shè)你正在爬樓梯。需要?n?階你才能到達(dá)樓頂。

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

解題思路

1. 通過對爬樓梯進(jìn)行分解，爬到當(dāng)前臺階的方式分為兩種，即由上一個臺階通過爬1和上兩個臺階爬2，同公式表示為:f(n) = f(n - 1) + f(n - 2);
2. 通過遞歸進(jìn)行爬樓（可能會重復(fù)計算導(dǎo)致超時）；
3. 尋找容器存儲遞歸過的值或通過for循環(huán)進(jìn)行有次數(shù)的累加。

代碼展示

class Solution {public int climbStairs(int n) {if(n == 1){return 1;}if(n == 2){return 2;}int first = 1;int second = 2;int ans = 0;for (int i = 2; i < n; i++){ans = first + second;first = second;second = ans;}return ans;}
}