1 题目
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，爬到顶部的方法有多少种？
样例 1：
输入：
n = 3输出：
3解释：共3种
- 1, 1, 1
- 1, 2
- 2, 1
样例 2：
输入：
n = 1输出：
1解释：只有一种方案
2 解答
错误的想法：
class Solution { public int climbStairs4(int n) { // 当 n=1 时返回1 if(n == 1) { return 1; } // 当 n=2 时返回2 if(n == 2) { return 2; } // 当 n 大于2时，返回 (n-1)的个数 + 1 这个思路有问题 // 比如 n=4的时候，n=3的情况有3种 + 1 也就是说 n=4的时候有4种情况 // 但是 n=4 的时候，不止4种情况 1+1+1+1 2+2 1+1+2 2+1+1 1+2+1 5种呢 // 所以这个思路行不通 return climbStairs(n - 1) + 1; } }
大神的想法：
public int climbStairs(int n) { int result = 0; switch(n){ case 1: result = 1; break; case 2: result = 2; break; case 3: result = 3; break; case 4: result = 5; break; case 5: result = 8; break; case 6: result = 13; break; case 7: result = 21; break; case 8: result = 34; break; case 9: result = 55; break; case 10: result = 89; break; case 11: result = 144; break; case 12: result = 233; break; case 13: result = 377; break; case 14: result = 610; break; case 15: result = 987; break; case 16: result = 1597; break; case 17: result = 2584; break; case 18: result = 4181; break; case 19: result = 6765; break; case 20: result = 10946; break; case 21: result = 17711; break; case 22: result = 28657; break; case 23: result = 46368; break; case 24: result = 75025; break; case 25: result = 121393; break; case 26: result = 196418; break; case 27: result = 317811; break; case 28: result = 514229; break; case 29: result = 832040; break; case 30: result = 1346269; break; case 31: result = 2178309; break; case 32: result = 3524578; break; case 33: result = 5702887; break; case 34: result = 9227465; break; case 35: result = 14930352; break; case 36: result = 24157817; break; case 37: result = 39088169; break; case 38: result = 63245986; break; case 39: result = 102334155; break; case 40: result = 165580141; break; case 41: result = 267914296; break; case 42: result = 433494437; break; case 43: result = 701408733; break; case 44: result = 1134903170; break; case 45: result = 1836311903; break; } return result; }
从上边大神的想法，就可以清晰的看出是斐波那契数列了哈：
递归想法（这个子还行不通过= =）：
class Solution { public int climbStairs(int n) { if(n <= 0){ return 0; } if(n == 1){ return 1; } if(n == 2){ return 2; } return climbStairs(n - 1) + climbStairs(n - 2); } }
最后的想法（两变量交替）：
class Solution { public int climbStairs(int n) { if (n <= 0) { return 0; } int a = 1, b = 1, sum; for(int i = 0; i < n - 1; i++){ sum = a + b; a = b; b = sum; } return b; } }
加油。