[编程题] lc:70. 爬楼梯

题目描述

输入输出例子

方法1：普通递归

思想：化为子问题

Java代码

//方法1：普通递归
    public int climbStairs(int n) {
        if(n==1){return 1;}
        if(n==2){
            return 2;
        }else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }

方法2：滑动数组

思想：让三个指针p q r，构成滑动数组，不断从右往左滑动；

Java代码

//方法2：滚动数组
    public int climbStaires2(int n){
        int p,q=0;int r=1;
        for (int i = 0; i < n; i++) {
            p = q;
            q = r;
            r = p+q;
        }
        return r;
    }

方法3：满足斐波那契直接使用数学公式

公式：

代码

//方法3：发现构造的这个数组符合斐波那契数列，直接用公式
    public static double climbStaires3(int n){
        int[] arr = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        double sqrt = Math.sqrt(5);
        return (int)(1/sqrt *(Math.pow((1+sqrt)/2,n+1)-Math.pow((1-sqrt)/2,n+1)));
    }

方法4：动态规划

思想：

代码

//动态规划
    public static double climbStaires4(int n){
        int[] arr = new int[n + 1];
        arr[0]=1;
        arr[1]=1;
        for (int i = 2; i <=n ; i++) {
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr[n];
    }

[编程题] lc[70. 爬楼梯

原文：https://www.cnblogs.com/jiyongjia/p/13338345.html