算法思想一:迭代
解题思路:
算法流程:
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