【刷题日记】70. 爬楼梯

本次刷题日记的第 10 篇，力扣题为：70. 爬楼梯 ，简单

一、题目描述：

前面做了一个中等题，我们来做一个简单题换换脑袋

这个题文字描述就少了许多，**但是看起来咋好像需要让我一个一个去列举？**不应该是这样，肯定有好方法

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

我们来看看这道题应该怎么做，我们傻傻的使用列举每一种情况的方式，那太傻了，请 kill 这种想法 ，我们来看看已知信息：

• 题目提供 n 级台阶，我们只能一次 爬 1 阶 或者 2 阶，那么爬到顶我们有几种方式？

乍一看这个题，如果我们在草稿纸上面列举每一种情况，那肯定是可以实现的，但是如果数据量变大了，我们也要自己去一一列举吗，这个就不太现实了

咱们要思考清楚每一步，才能让计算机去执行我们的想法

看到这个题，xdm 可能会从头看是想，1 阶 ， 2 阶 ， 4 阶 .... ，何时才是一个头？

那么，我们可以反过来思考，假如台阶为  n 级， 那么我最后一步上台阶的方式要么是走 1 阶，要么是走 2 阶， 不能再多了

所以 走 n 级台阶的方式是等于 走 n-1 级台阶方式  加上 走 n-2 级台阶的方式， 即：

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)

这里我们知道，  n  是 大于等于 1 的

就这样一直推下去，一直滚动下去，那么咱们来计算 n 级台阶的时候就很容易了 ， 直接将逻辑翻译成代码即可

2、尝试编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func climbStairs(n int) int {
    if n == 1 || n == 2 {
        return n
    }
    var i,j,r = 0,1,2
    for k :=3 ; k <= n; k++ {
        i = j
        j = r
        r = i+j
    }
    return r
}

f(1) 和 f(2)  咱们直接知道具体值是多少了，直接从 3 开始推演和计算即可

四、总结：

本题比较简单，主要是换换脑袋，换种方式来看问题，时间复杂度是 O(n) , 空间复杂度是 O(1)

原题地址：70. 爬楼梯

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~