LeetCode 70. 爬楼梯 Climbing Stairs

【题目描述】
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

【示例1】

输入： 1
输出： 1
解释： 有1种方法可以爬到楼顶。
1.  1 阶 

【示例2】

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

【示例3】

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

【思路】
1、有规律可循 类似斐波那契数列
2、可以使用递归 不过性能很差
3、使用迭代 f(n) = f(n-1) + f(n-2)
4、时间复杂度O(n)
5、空间复杂度O(n)

Swift代码实现:

func climbStairs(_ n: Int) -> Int {
    if n <= 2 {
        return n
    }
    var tmp = n
    var step = 0,a = 1,b = 2
    while tmp > 2 {
        step = a+b
        a = b
        b = step
        tmp-=1
    }
    return step
}

后续会继续更新文章，也可以关注我的公众号：

个人公号.jpg