70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
 

提示：

1 <= n <= 45

解题思路：因为1<=n<=45，也可以用打表的方式解题，

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;
}

或者：

    public int climbStairs(int n) {
        return new int[]{
                0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
        }[n];
    }

不过还是推荐根据：f(x)=f(x−1)+f(x−2)

也就是说爬到第 x级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第x−2 级台阶的方案数的和，因为从第0级到1级只有一种方案，从0级到2级有2种方案，从1级到2级有一种方案，也就是当前的层级等于前面两个层级的累加。

可以说，当遇到那种每次进行1或2的试探时可以考虑一下是否符合爬楼梯的思路。

即：

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

 

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 

提示：

0 <= n <= 30

 解题思路：看着这0 <= n <= 30的范围我陷入了沉思......

打表： 

class Solution {
    public int fib(int N) {
        if(N==0)
            return 0;
        if(N==1)
            return 1;
        if(N==2)
            return 1;
        if(N==3)
            return 2;
        if(N==4)
            return 3;
        if(N==5)
            return 5;
        if(N==6)
            return 8;
        if(N==7)
            return 13;
        if(N==8)
            return 21;
        if(N==9)
            return 34;
        if(N==10)
            return 55;
        if(N==11)
            return 89;
        if(N==12)
            return 144;
        if(N==13)
            return 233;
        if(N==14)
            return 377;
        if(N==15)
            return 610;
        if(N==16)
            return 987;
        if(N==17)
            return 1597;
        if(N==18)
            return 2584;
        if(N==19)
            return 4181;
        if(N==20)
            return 6765;
        if(N==21)
            return 10946;
        if(N==22)
            return 17711;
        if(N==23)
            return 28657;
        if(N==24)
            return 46368;
        if(N==25)
            return 75025;
        if(N==26)
            return 121393;
        if(N==27)
            return 196418;
        if(N==28)
            return 317811;
        if(N==29)
            return 514229;
        if(N==30)
            return 832040;
        return 0;
    }
}

上一题一样的写法：

class Solution {
    public int fib(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        int a0=0,a1=1,r=0;
        for(int i=2;i<=n;i++){
            r=a0+a1;
            a0=a1;
            a1=r;
        }
        return r;
    }
}

总结：万物皆可斐波那契......

---

近日总结：马上要5月份了，焦虑......