描述
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?
Note: Given n will be a positive integer.
分析
設(shè) f (n) 表示爬 n 階樓梯的不同方法數(shù)，為了爬到第 n 階樓梯，有兩個(gè)選擇: ? 從第n?1階前進(jìn)1步; ? 從第n?1階前進(jìn)2步; 這是一個(gè)斐波那契數(shù)列。 方法 1：遞歸，太慢; 方法 2：迭代，也可以看作動(dòng)態(tài)規(guī)劃。 方法3：數(shù)學(xué)公式。斐波那契數(shù)列的通項(xiàng)公式為
代碼
// 迭代，時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)class Solution {public: int climbStairs(int n) { int PRev = 0; int cur = 1; for (int i = 1; i <= n; ++i) { int tmp = cur; cur += prev; prev = tmp; } return cur; }};// 數(shù)學(xué)公式，時(shí)間復(fù)雜度O(1)，空間復(fù)雜度O(1)class Solution {public: int climbStairs(int n) { const double s = sqrt(5); return floor((pow((1+s)/2, n+1) - pow((1-s)/2, n+1)) / s ); }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
