題目

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

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

解題思路

1. 通過(guò)對(duì)爬樓梯進(jìn)行分解，爬到當(dāng)前臺(tái)階的方式分為兩種，即由上一個(gè)臺(tái)階通過(guò)爬1和上兩個(gè)臺(tái)階爬2，同公式表示為:f(n) = f(n - 1) + f(n - 2);
2. 通過(guò)遞歸進(jìn)行爬樓（可能會(huì)重復(fù)計(jì)算導(dǎo)致超時(shí)）；
3. 尋找容器存儲(chǔ)遞歸過(guò)的值或通過(guò)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;}
}