数据结构与算法-004-数组-爬楼梯

题目描述

• 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
• 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
• 注意：给定 n 是一个正整数。
• 题目来自leetcode

暴力解法

    // leetcode 上会执行超时，求30以内还可以，45就直接跪了
    public int climbStairs(int n) {
        // 暴力法,时间复杂度为指数级,O(2^n),也可记做 O(k^n),k 为每一层展开数列，斐波那契每次展开2个数，所以记做O(2^n)
        // 题的本质是求斐波那契
        // 斐波那契额公式： fib=f(n-1)+f(n-2);
        int count=0;
        if(n<=2){
            return n;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }

较优解-动态规划-leetcode官方题解

public int climbStairs(int n) {
        // 官方题解-动态规划，时间复杂度 O(n)
        // 斐波那契数列公式 fib(n)=f(n-1)+f(n-2)
        // 本题问的是有多少种走法
        // 问题分解
        // 0 阶 = 0 种
        // 1 阶 = 1 种，即 爬 1 阶
        // 2 阶 = 2 种，即 爬 1*2 阶 或 爬2阶
        // 3 阶 = 3 种，即 爬 1*3 阶、爬 1 + 2 阶、爬 2 + 1 阶
        // 4 阶 = 5 种，即 爬 1*5 阶、爬 1 + 2*2 阶、爬 1*2 + 2 + 1 阶。。。。
        // n 阶 = n 之前所有阶数解法的总和
        // 所以 n 阶有多少种爬法可以简化为 x = a + b, a=上一次b的值,b=上一次x的值，相当于记忆化旧的值，初始值a、b均为0，这样循环 n 次后x 值始终是累加的，最终得出爬 n 阶台阶的总数
        // 小于等于3的时候，计算结果就是 n
        if(n<=3){
            return n;
        }
        // 初始 a\b 没区别, x 初始化为 1 是最少要有一种爬法
        int i=0,a=0,b=0,x=1;
        while(i<n){
            a = b; 
            b = x; 
            x = a + b;
            i++;
        }
        return x;
    }

通常暴力部分由自己解答，较优解通常是自己对官方题解的理解，各位看官觉得哪理解不对欢迎来喷