文章收录于LeetCode专栏

---

爬楼梯

题目

  假设你正在爬楼梯，需要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 阶

题解

  第一步审题，典型的爬楼梯问题，第一反应斐波拉契数列，采用动态规划分解问题，找到最近子问题。

  第二步列出所有解，斐波拉契f(n) = f(n−1)+f(n−2)。

class Solution{
    public int climbStairs(int n){
        if(n == 1 || n == 2){
            return n;
        }
        int n1 = 1;
        int n2 = 2;
        for(int i=3; i<=n; i++){
            int temp = n1 + n2;
            n1 = n2;
            n2 = temp;
        }
        return n2;
    }
}

  第三步时间复杂度和空间复杂度分析，因为进行了一次遍历和没有使用任何额外的内存空间，所以空闲复杂度为O(1)，时间复杂度为O(n)。

---

一键三连，让我的信心像气球一样膨胀！