题解 | #跳台阶#

算法思想一：迭代

解题思路：

算法流程：
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阶

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

代码展示：

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