题目:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。 - 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
看到这题, 脑子里想到的就是动态规划, 什么是动态规划, 一言以蔽之就是, 记住你已经做过的计算, 在已经计算过的基础上叠加, 避免重复的计算.
首先, 不妨将阶梯数想象成一个全是1组成的数组, 比如8级阶梯, 就是:
[1, 1, 1, 1, 1, 1, 1, 1]
那么不同的爬楼梯方案就类似于:
[2, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1] ......
当只有一个阶梯走跨两步时, 就可能出现7中情况, 即:
[2, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1], [1, 1, 2, 1, 1, 1, 1], [1, 1, 1, 2, 1, 1, 1] ......
而当两个阶梯走跨两步时, 可能出现如下情况:
[2, 2, 1, 1, 1, 1], [2, 1, 2, 1, 1, 1], [2, 1, 1, 2, 1, 1], [2, 1, 1, 1, 2, 1], [2, 1, 1 ,1, 1, 2],
[1, 2, 2, 1, 1, 1], [1, 2, 1, 2, 1, 1], [1, 2, 1, 1, 2, 1], [1, 2, 1, 1, 1, 2],
[1, 1, 2, 2, 1, 1], [1, 1, 2, 1, 2, 1], [1, 1, 2, 1, 1, 2]
......
注意到这里两次跨两步的情况都是在一次跨两步的基础下得的出来的, 具体就是在一次跨两步的那个两步之后选择跨两步的位置, 这样避免出现重复的跨步情况, 又能完整遍历出结果, 基于这个方案, 我写出了第一种算法
func climbStairs(_ n: Int) -> Int {
if n > 0 {
var count = 1
for i in 1..<n {
count += self.climbStairs(n - i - 1)
}
return count
} else {
return 1
}
}
每个台阶总数全为1, 是一种情况, 然后在这个全为一的数组中凑出一个2,
得到多种情况, 在每种情况下, 将凑出的那个2去掉, 使2之后剩下的1成为一个新的值, 向下递归, 直到n = 0, 这个时候我们知道, 只有1种情况
但是很不幸这种方式超时了, 因为里面还是包含了太多的重复计算
以数字8为例:
当我们传入一个8, 他将递归计算值为6, 5, 4, 3, 2, 1, 0的结果
而计算6, 则将递归计算4, 3, 2, 1, 0的结果
计算5将计算3, 2, 1, 0的结果
...
可以看到, 0的结果, 1的结果, 2的结果将被重复计算多次, 而这些计算是不需要的
于是我重新观察这种方案, 当n = 0时, 可以直接得出1, 当n = 1时可以直接得出1, 当n = 2时, 可以视为 1 + (n = 0), 以此类推:
n = 0: 1
n = 1: 1
n = 2: 1 + (n = 0)
n = 3: 1 + (n = 1) + (n = 0)
n = 4: 1 + (n = 2) + (n = 1) + (n = 0)
n = 5: 1 + (n = 3) + (n = 2) + (n = 1) + (n = 0)
...
可以观察到:
n = 4: (n = 3) + (n = 2)
n = 5: (n = 4) + (n = 3)
于是可以通过累加法, 从n = 2开始
记下n = 0 和 n = 1
n = 2 就等于 (n = 0) + (n = 1)
记下n = 1 和 n = 2
n = 3 就等于 (n = 2) + (n = 1)
记下n = 2 和 n = 3
n = 4 就等于 (n = 3) + (n = 2)
...
最终得出答案
func climbStairs(_ n: Int) -> Int {
if n > 1 {
var lastTwo = 1
var addCount = 1
for index in 2...n {
let tLast = lastTwo
lastTwo = addCount
addCount += tLast
}
return addCount
} else {
return 1
}
}
提交通过
网友评论