本文共 3169 字，大约阅读时间需要 10 分钟。
:-: 9.1 爬楼梯
* * * * *
**题干：**
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
~~~
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
~~~
示例 2：
~~~
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
~~~
**题目分析：**
如果放在中学课堂之上，这就是一个典型的排列组合问题，所以我们可以采用排列组合的方式来解决这个问题，但是这个方法处理次数在随着n的增加，急剧增长，虽然现在我们的电脑处理速度快，但是我们也不应该这样伤害它呀！我们再来分析一下，当n = 1的时候，f(1) = 1；当n = 2的时候，f(2) = 2；当n = 3的时候，f(3) = 3；当n = 4的时候，f(4) = 5，我们发现f(n) = f(n - 1) + f(n - 2)。这个时候我们可以发现这不就是个斐波那契数列吗？我们可以采用递归的方式来做呀，再看斐波那契数列函数，也是动态规划方程呀。
**新手有可能遇到的解题思路陷阱：**
就是上文所提到的排列组合方法，此方法属于暴力枚举，时间复杂度是值数级。坚决不推荐此方法(并不是其他的算法题用排列组合就不好，单指此题)。
**解题思路分析以及代码实现：**
第一种思路：排列组合(不推荐)，方法中使用long类型，是因为当n = 14以后，nums函数会出现int范围越界，所以采用了long类型。
第一种思路代码：
~~~
public long climbStairs(int n) {
if (n <= 0) {
return (long) 0;
} else {
long sum = 0;
int two = n / 2;// 计算2的个数
int one = n % 2;// 计算当2最多是1的个数
for (long i = two; i >= 0; i--) {
// 减1个2增加两个1
sum += nums(one + 2 * (two - i), i);
}
return sum;
}
}
public static long nums(long one, long two) {
// x1是1的个数，x2是2的个数
long down = 1;
long up = 1;
for (int i = 1; i <= one; i++) {
down *= i;
}
for (long i = one + two; i > two; i--) {
up *= i;
}
return up / down;
}
~~~
**复杂度分析**
时间复杂度：O(n^2)。
空间复杂度：O(1)。
第二种思路：递归，我们要是想上n这个台阶，我们要么是在n - 1这个台阶上，要么是在n - 2这个台阶上，然后问题就变为我们怎么到n - 1或n - 2这个台阶上，直至我们分析到n = 1或n = 2时，我们会发现f(n) = f(n - 1) + f(n - 2),由此可写递归算法。
第二种思路代码：
~~~
public int climbStairs(int n) {
if (n < 1)
return 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
//另一种实现方式
/*return (n == 1 || n == 2) ? n : climbStairs(n - 2) + climbStairs(n - 1);*/
}
~~~
**复杂度分析**
时间复杂度：O(2^n)。
第三种思路：递归+备忘录，但是我们再分析下上面这个递归算法，f(n) = f(n - 1) + f(n - 2)，f(n - 1) = f(n - 2) + f(n - 3)，f(n - 2) = f(n - 3) + f(n - 4)，我们发现什么特别的东西有，我们发现他进行了大量的重复计算，这怎么可以呢？
:-: 
我们要避免这种无用功，我们可以这样做，利用缓存的思想，把值都存起来，等需要用的时候，直接拿来用，不去进行耗时耗力的计算了
第三种思路代码：
~~~
public int climbStairs(int n) {
Map map = new HashMap();
//List集合也可以，但是要标好位置。
if (n < 1)
return 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
if (map.containsKey(n)) {
return map.get(n);
}
int sum = climbStairs(n - 1) + climbStairs(n - 2);
map.put(n, sum);
return sum;
}
~~~
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
第四种思路：动态规划算法，不使用递归方式，我们将思路逆转过来，自下而上的推理，我们由以上分析发现当n = 1的时候，f(1) = 1；当n = 2的时候，f(2) = 2；当n = 3的时候，f(3) = 3；当n = 4的时候，f(4) = 5，我们发现f(n) = f(n - 1) + f(n - 2)，我们所求的当前台阶只和它后后两个台阶发生关系。
第四种思路代码：
~~~
public int climbStairs(int n) {
if (n < 1)
return 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
int sum[] = new int[n];
sum[0] = 1;
sum[1] = 2;
for (int i = 2; i < n; i++) {
sum[i] = sum[i - 1] + sum[i - 2];
}
return sum[n - 1];
}
~~~
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
第五种思路：迭代法(状态压缩法，滚动数组法、滑动窗口法等)，还是和第四种一样的思想，我们所求的当前台阶只和它后后两个台阶发生关系，只要保证我们现在所求的当前台阶后的两个台阶就可以了。同时也是优化空间复杂度。
第五种思路代码：
~~~
public int bestStairs(int n) {
if (n < 1)
return 0;
if (n == 1)
return 1;
if (n == 2)
return 2;
int sum = 0, sum1, sum2;
sum1 = 1;
sum2 = 2;
for (int i = 2; i < n; i++) {
sum = sum1 + sum2;
sum1 = sum2;
sum2 = sum;
}
return sum;
}
~~~
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(1)。
**若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**
转载地址：http://kznva.baihongyu.com/