算法思想一:迭代

解题思路:

算法流程:
1、当 n <= 2时,直接返回 n
2、设置两个变量 fone = 1, ftwo = 2
3、循环
    1、计算前两个数字之和
    2、将前两个数字更新 ;
4、循环结束返回最终结果 fn
图解:

代码展示:

Python版本

class Solution:
    def jumpFloor(self, number):
        # write code here
        # 特殊情况
        if number <= 2: 
            return number 
        fone = 1 
        ftwo = 2 
        # 迭代计算 
        for i in range(3, number+1): 
            fn = ftwo + fone 
            fone = ftwo 
            ftwo = fn 
        return fn

复杂度分析

时间复杂度:算法迭代n次,n表示number

空间复杂度:使用额外常数级空间

算法思想二:动态规划

解题思路:

本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和
1、爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
2、爬上 n-2 阶楼梯的方法数量,因为再爬2阶就能到第n阶

所以可以得到公式
同时需要初始化

代码展示:

JAVA版本
public class Solution {
    public int jumpFloor(int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= target; i++) { 
            dp[i] = dp[i - 1] + dp[i - 2]; 
        } 
        return dp[target]; 
    } 
}


复杂度分析

时间复杂度:算法循环n次

空间复杂度:额外数组占用空间

注:此题解法与 NC65 斐波那契数列 相同,可以参考题解 https://blog.nowcoder.net/n/d8d1e7cdc0594b8098818b5e72c7953f