前端积累

# 爬楼梯

# 难度：简单

# 描述：

假设你正在爬楼梯，需要 n 步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

# 样例：

比如 n=3，1+1+1=1+2=2+1=3，共有 3 种不同的方法

返回 3

# 思路分析：

这类题我们首先要来找其中的规律，找到了里面的规律，剩下的就好办了。

我再列举出几个结果：

0 =0 0种方法
1 = 1 种方法
2 = 1+1 =2 2种方法
3=1+1+1=1+2=2+1 3种方法
4 = 1*4 = 1+2+1 = 1+1+2 = 2+1+1 = 2+2 5种方法
5 = 1*5 = 2+1+2 =2+2+1 = 1+2+2 =1+2+1+1 = 1+1+2+1 = 2+1+1+1 = 1+1+1+2 8种方法
1
2
3
4
5
6

想一下他们的规律，试着自己做出来。

# 代码模板：

/**
 * @param n: An integer
 * @return: An integer
 */
const climbStairs = function(n) {}
1
2
3
4
5

# 想一想再看答案

# 想一想再看答案

# 想一想再看答案

# 规律：

这道题的规律实际上跟之前做的查找斐波纳契数列中第 N 个数中的规律有点类似。

斐波纳契数列中第 N 个数的规律

前 2 个数是 0 和 1,第 i 个数是第 i-1 个数和第 i-2 个数的和。

本题中的规律是：

除了 1 阶楼梯和 2 阶楼梯是一种和两种方法之外，第 n 阶的楼梯的方法是第 i-1 阶楼梯和第 i-2 阶楼梯所用方法的和。

# 代码：

解题的核心就是逐步推导，推导出 n 前面的两个值。

  1. 数组：
const climbStairs = function(n) {
	let dp = [0, 1, 2] // 初始数组 前面三个没有规律
	for (let i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] // 从3开始都是可以由前面两个元素相加推导出来
	}
	return dp[n]
}
console.log(climbStairs(3), climbStairs(4), climbStairs(5))
1
2
3
4
5
6
7
8
  1. 递归：
const climbStairs = function(n) {
	function item(n) {
		// 循环退出条件
		if (n === 1) return 1
		if (n === 2) return 2
		return item(n - 1) + item(n - 2) // 将递归到1个楼梯和两个楼梯 最后反推到n个楼梯
	}
	return item(n)
}
console.log(climbStairs(3), climbStairs(4), climbStairs(5))
1
2
3
4
5
6
7
8
9
10
  1. 交换变量：

实际上我们只需要 n 之前的两个值，就可以求出 n 所用的方法，所以我们没必要将 n 之前的所有值都推导出来。

所以我们只需要保存这两个值，然后再求出第三个值就可以了。

const climbStairs = function(n) {
	// 前两个值的返回结果
	if (n === 1) return 1
	if (n === 2) return 2
	let a = 1, // 1阶楼梯
		b = 2, // 2阶楼梯
		c
	for (let i = 3; i <= n; i++) {
		c = a + b // n的结果
		// 为了后续推导，不断保存前两个值
		a = b
		b = c
	}
	return c
}
console.log(climbStairs(3), climbStairs(4), climbStairs(5))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实际上，我们也可以使用 ES6 的交换变量方法，而不用声明第三个变量：

const climbStairs = function(n) {
	// 前两个值的返回结果
	if (n === 1) return 1
	if (n === 2) return 2
	let a = 1,
		b = 2
	for (var i = 3; i <= n; i++) {
		;[a, b] = [b, b + a]
	}
	return b
}
console.log(climbStairs(3), climbStairs(4), climbStairs(5))
1
2
3
4
5
6
7
8
9
10
11
12

# 点个Star支持我一下~

← 数组中的最长单词 →