:-: 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<Integer, Integer> map = new HashMap<Integer, Integer>(); //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)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**