经典爬楼梯算法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶，2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶，1 阶 + 2 阶，2 阶 + 1 阶

首先分析题目推测数值
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
f(5) = 8
推断结果值为一个不标准的斐波那契数列
进一步分析因为一次只能爬1或者2个台阶
当 n>=3的时候,
我们分析：第一步可以走1步，或者走2步 走一步之后我们还剩 n-1步的台阶需要走，走2步还剩n-2步台阶
因此可以定义状态方程

n=1时 f(1) = 1
n=2时 f(2) = 2
n>=3时 f(n) = f(n-2)+f(n-1)

我们可以很容易想到一个标准的递归

public int climbStairs(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else if(n>=3){
            return climbStairs(n-1)+climbStairs(n-2);
        }else {
            return -1;
        }
    }

递归求解相当于构建一个二叉树，然后遍历所有节点，因此
时间复杂度O(2^n)，空间复杂度相当于二叉树的高度n O(n)
由于时间复杂度太高，当n值很大的时候计算次数会爆炸！！
分析问题之后修改代码逻辑如下

public int climbStairs(int n) {
       int[]nums = new int[n];
        int result = 0;
        for(int i=1;i<=n;i++){
            if(i==1){
                result = 1;
            }
            if(i == 2){
                result = 2;
            }
            if(i>=3){
                result = nums[i-2]+nums[i-3];
            }
            nums[i-1] = result;
        }
        return result;
    }

将每一次循环中生成的f(n)保存到数组中，后续计算f(n+1)直接从数组中获取之前保存的数值相加
如此将时间复杂度变为O(n),空间复杂度为数组的长度O(n);
然后查询网上其他算法，发现可以使用尾递归来进一步压缩空间复杂度为O(1)

 public int climbStairs(int n) {
        return fib(1,2,n);
    }

    public int fib(int first,int second,int n){
        if(n==1){
            return first;
        }
        if(n==2){
            return second;
        }
        if(n==3){
            return first+second;
        }
        return fib(second,first+second,n-1);
    }