LeetCode第67题
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 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)。即一个问题可以分解为同样性质的两个子问题。这时候最先想到的是采用递归来做。但是依据递归树，发现很多分支重复计算。
于是想到利用一个数组将已经计算出的存起来。如果只需要最后的结果，中间的结果不需要，那么可以用两个数组变量暂存f(n-1)和f(n-2)，这样就优化了空间复杂度。
源代码
//解法一：用数组存储每一个的结果
int climbStairs(int n){
static int climbStair[100] = {0}; //创建数组，存储已经计算出1-n阶楼梯的走法数，初始化为0
if(climbStair[n] != 0){ //如果之前已经计算出结果
return climbStair[n];
}
else{
if(n <= 1){
climbStair[n] = 1;
return 1;
}
else{
climbStair[n] = climbStairs(n - 1) + climbStairs(n - 2);
return climbStair[n];
}
}
}
//解法二：空间优化的写法
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;
}
分析
时间复杂度为O（n），采用解法一的空间复杂度为O（n），采用解法二的空间复杂度为O（1）。
