Java教程

爬楼梯----(算法学习笔记21.5.23)

本文主要是介绍爬楼梯----(算法学习笔记21.5.23),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

有这样一个问题:

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

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

思考 当只有一层的时候只有一个方法,当有两层的时候有两个方法,当有三层的时候有三个方法,因此我们不难发现,n阶的爬法呈现出斐波那契数列,到n阶时的方法设为f(n) = f(n-1) + f(n-2)

因此我的思路就是用斐波那契数列求和来求解方法

第一次书写是应用递归法求解,代码如下:

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

但是在执行过程中出现了问题---------------超出时间限制

由于消耗时间过长,我不得不采用另一种方法来求和

我的思路是建立一个数组arr arr[0]对应第一项,arr[1]对应第二项,以此类推,在重写了方法之后,代码如下:

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

由于第一项对应foot[0],第二项对应foot[1],所以最后输出的应该是foot[n-1];很显然,该段代码很快通过了检测。

若有其他方法,希望各位大神指导.

 

 

 

 

这篇关于爬楼梯----(算法学习笔记21.5.23)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!