题解 | #跳台阶#

算法思想一：迭代

解题思路：

算法流程：
1、当 n <= 2时，直接返回 n
2、设置两个变量 fone = 1, ftwo = 2
3、循环
1、计算前两个数字之和 $fn = fone + ftwo$
2、将前两个数字更新 $fone = ftwo$ ; $ftwo = fn$
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

复杂度分析

时间复杂度 $O(N)$ ：算法迭代n次，n表示number

空间复杂度 $O(1)$ ：使用额外常数级空间

算法思想二：动态规划

解题思路：

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

所以可以得到公式 $dp[n] = dp[n-1] + dp[n-2]$
同时需要初始化 $dp[0]=1$ 和 $dp[1]=1$

代码展示：

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]; 
    } 
}

复杂度分析

时间复杂度 $O(N)$ ：算法循环n次

空间复杂度 $O(N)$ ：额外数组占用空间

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