LeetCode第67題
題目描述：
假設(shè)你正在爬樓梯娩梨。需要 n 階你才能到達樓頂汰具。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢届氢？
注意：給定 n 是一個正整數(shù)忌锯。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂枯夜。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂斩启。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/climbing-stairs
思路
遞推表達式為f(n) = f(n-1) + f(n-2)夜牡。即一個問題可以分解為同樣性質(zhì)的兩個子問題商架。這時候最先想到的是采用遞歸來做堰怨。但是依據(jù)遞歸樹，發(fā)現(xiàn)很多分支重復(fù)計算蛇摸。
于是想到利用一個數(shù)組將已經(jīng)計算出的存起來备图。如果只需要最后的結(jié)果，中間的結(jié)果不需要赶袄，那么可以用兩個數(shù)組變量暫存f(n-1)和f(n-2)诬烹，這樣就優(yōu)化了空間復(fù)雜度。
源代碼
//解法一：用數(shù)組存儲每一個的結(jié)果
int climbStairs(int n){
static int climbStair[100] = {0}; //創(chuàng)建數(shù)組弃鸦，存儲已經(jīng)計算出1-n階樓梯的走法數(shù)绞吁，初始化為0
if(climbStair[n] != 0){ //如果之前已經(jīng)計算出結(jié)果
return climbStair[n];
}
else{
if(n <= 1){
climbStair[n] = 1;
return 1;
}
else{
climbStair[n] = climbStairs(n - 1) + climbStairs(n - 2);
return climbStair[n];
}
}
}
//解法二：空間優(yōu)化的寫法
int climbStairs(int n){
//遞推公式f(n) = f(n-1) + f(n-2)
//用兩個變量分別代表f(n-1)和f(n-2)
int stairs_1 = 2;
int stairs_2 = 1;
int tmp = n;
int i;
for(i = 3;i <= n;++i){
tmp = stairs_1 + stairs_2; //f(n) = f(n-1) + f(n-2)
stairs_2 = stairs_1;
stairs_1 = tmp;
}
return tmp;
}
分析
時間復(fù)雜度為O（n），采用解法一的空間復(fù)雜度為O（n）唬格，采用解法二的空間復(fù)雜度為O（1）家破。
