# 70. Climbing Stairs

{% embed url="<https://leetcode.com/problems/climbing-stairs/>" %}

n 只要是大于等于 2 的数，最后一步就只可能是 2 或 1，则走 n 阶的方法只有两大类：

1. 最后走1步的
2. 最后走2步的

也就是说： `f(n) = f(n-1) + f(n-2)`

即 fibonacci 数列。

{% tabs %}
{% tab title="fibonacci - A" %}

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        # f(n) = f(n-1) + f(n-2)
        if n <= 2: return n
        f = [0 for _ in range(n+1)]
        f[1], f[2] = 1, 2
        
        for i in range(3, n+1):
            f[i] = f[i-1] + f[i-2]
            
        return f[n]
```

{% endtab %}

{% tab title="fibonacci - B" %}

```python
class Solution:
    def climbStairs(self, n):
        a,b = 1,0
        for _ in range(n):
            a,b = a+b,a
        return a
```

{% endtab %}

{% tab title="" %}

```
```

{% endtab %}
{% endtabs %}
