爬楼梯 java

题目描述要求思路

递推条件

引入数组三个变量 硬推

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1 <= n <= 45 思路 递推条件

倒着思考一下，如果现在我只要走最后一步的时候，即1阶或2阶，记需要 n 阶你才能到达楼顶有sum(n)不同的方法,故只要知道上一步行走的所有可能就可以了，显然sum(n)=sum(n-1)+sum(n-2),显然满足斐波那契数列的通式条件

class Sulation{
public int climbStairs(int n) {
    int[] num = new int[n + 1];
    num[0] = 1;
    num[1] = 1;
    for (int i = 2; i <= n; i++) {
        num[i] = num[i - 1] + num[i - 2];
    }
    return num[n];
    }
}

class Sulation{
public int climbStairs(int n) {
    int a = 1;
    int b = 1;
    int c = 0;
    for (int i = 2; i <= n; i++) {
       c=a+b;
       b=c;
       a=b;
    }
    return c;
    }
}

第一项：1
第二项：2
第三项：3
第四项：5
第五项：8
… …

大胆猜测一下最后一项为前两项之和