# Climbing Stairs

### 描述​

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

### 分析​

f(n)表示爬n阶楼梯的不同方法数，为了爬到第n阶楼梯，有两个选择：

• 从第n-1阶前进 1 步；
• 从第n-1阶前进 2 步；

### 代码​

#### 1. 动规​

// Climbing Stairs// Time Complexity: O(n)// Space Complexity: O(n)public class Solution {    public int climbStairs(int n) {        if (n == 1) {            return 1;        }        int[] dp = new int[n + 1];        dp[1] = 1;        dp[2] = 2;        for (int i = 3; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }}

#### 2. 迭代​

// Climbing Stairs// 迭代，时间复杂度O(n)，空间复杂度O(1)public class Solution {    public int climbStairs(int n) {        int prev = 0;        int cur = 1;        for(int i = 1; i < n+1 ; ++i){            int tmp = cur;            cur += prev;            prev = tmp;        }        return cur;    }};

#### 3. 数学公式​

// Climbing Stairs// 数学公式，时间复杂度O(1)，空间复杂度O(1)public class Solution {    public int climbStairs(int n) {        final double s = Math.sqrt(5);        return (int)Math.floor((Math.pow((1+s)/2, n+1) +            Math.pow((1-s)/2, n+1))/s + 0.5);    }};