内容简介:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1:示例 2:每次可以爬 1 或 2 个台阶。当我们爬 4 个台阶时,就是爬 3 个台阶的方法数,加上爬 2 个台阶的方法数,等于 F(3) + F(2) = 3 + 2 = 5。所以当我们爬 N 个台阶,就有 F(N - 1) + F(N - 2) 种方法。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1:
输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 复制代码
示例 2:
输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 复制代码
思路
每次可以爬 1 或 2 个台阶。当我们爬 4 个台阶时,就是爬 3 个台阶的方法数,加上爬 2 个台阶的方法数,等于 F(3) + F(2) = 3 + 2 = 5。所以当我们爬 N 个台阶,就有 F(N - 1) + F(N - 2) 种方法。
解决方案
方案一:暴力破解
我们可以用递归的方法得到所有小于N的方法数,并把它们相加得出结果。递归结束的标志为 N=1 或 N =2。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
return climbStairs(n - 1) + climbStairs(n - 2)
};
复制代码
时间复杂度 O( )。这种暴力解题的方法会超出时间限制,显然不是我们想要的。
方案二:优化暴力破解
从上一种方法我们可以发现,每一步的结果都做了上一步的重复计算。比如F(6) + F(5) 后会计算 F(5) + F(4),F(5) 我们已经计算过了,就不要重复计算了。所以我们可以用一个数组来储存计算结果,方便重复利用。
var climbStairs = function(n) {
let arr = []
function climb(n) {
if (n == 1) return 1
if (n == 2) return 2
if (arr[n] > 0) return arr[n]
arr[n] = climb(n - 1) + climb(n - 2)
return arr[n]
}
return climb(n)
};
复制代码
时间复杂度 O(n),优化之后提高了速度,已经不会超出时间限制了。
方案三:问题分解
和递归的思路一样,把一个大问题分解成多个小问题,只是这次我们使用循环的方式,减少内存的开销。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
let arr = []
arr[1] = 1
arr[2] = 2
for (let i = 3; i<= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr[n]
};
复制代码
时间复杂度 O(n),优化了内存的消耗,速度没有提升。
方案四:斐波那契数
从上一个方案我们可以看出这是一个斐波那契数列。
var climbStairs = function(n) {
if (n == 1) return 1
if (n == 2) return 2
let first = 1
let second = 2
for (let i = 3; i<= n; i++) {
let third = first + second
first = second
second = third
}
return second
};
复制代码
时间复杂度 O(n)
以上所述就是小编给大家介绍的《LeetCode70 —— 爬楼梯》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
程序设计方法(中文版)
Matthias Fellisen / 黄林鹏、朱崇恺 / 人民邮电出版社 / 2003-12 / 49.00元
《程序设计方法》以Scheme语言为基础介绍计算和程序设计的一般理论和实践。《程序设计方法》由8个部分和7个独立的章节(第8、13、18、24、29、33、38章)组成。8个部分主要讨论程序设计,独立章节则介绍一些与程序设计和计算相关的话题。《程序设计方法》第1至第3部分介绍了基于数据驱动的程序设计基础。第4部分介绍了程序设计中的抽象问题。第5部分和第6部分是与递归及累积相关的内容。《程序设计方法......一起来看看 《程序设计方法(中文版)》 这本书的介绍吧!