美文网首页
经典爬楼梯算法

经典爬楼梯算法

作者: akkaMQ | 来源:发表于2019-11-27 11:02 被阅读0次

假设你正在爬楼梯。需要 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);
    }

相关文章

  • 经典爬楼梯算法

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

  • 第20章 动态规划入门

    1、蒜头君爬楼梯(一) 算法分析 时间复杂度 Java 代码 2、蒜头君爬楼梯(二) 算法分析 时间复杂度 Jav...

  • 算法-爬楼梯

    如果爬楼梯需要 n 阶你才能到达楼顶。( n 是一个正整数)每次你可以爬 1 或 2 个台阶。你有多少种不同的方法...

  • 算法—爬楼梯

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

  • 常见算法

    一、【经典算法大全】收集51种经典算法 初学者必备

  • 算法-爬楼梯问题

    一个N阶的楼梯,每次能1或着2阶,问走n阶的楼梯有多少种走法? 分析可知在走第n阶的时候,是与第n-1阶和n-2阶...

  • 算法:爬楼梯 - Swift

    题目:你正在爬楼梯。需要 n 步你才能到达顶部。每次你可以爬 1 或 2 个台阶。你有多少种不同的方式可以爬到楼顶...

  • 12月,献上的12本Java架构师必读书籍

    经典算法谜题的合集Google、Facebook等一流IT公司算法面试必备 《算法谜题》是经典算法谜题的集结。它列...

  • 算法学习记录

    可视化算法 白话经典算法

  • 学习路线规划

    目前有两本书,《算法竞赛入门经典》和《算法竞赛进阶指南》。根据书名应该先看《算法竞赛入门经典》( 《算法竞赛入门经...

网友评论

      本文标题:经典爬楼梯算法

      本文链接:https://www.haomeiwen.com/subject/kbnuwctx.html