# 【LeetCode】 70. Climbing Stairs

## Description
> 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?
> Note: Given n will be a positive integer.

> 你正在爬樓梯。到頂端總共有n階。
> 每次你都可以爬1或是2階，請問你總共有幾種不同的方法爬到頂呢？
> 提醒：n只會是正整數。

## Example:

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

## Solution

* 最基本的遞迴問題，第`n`階會是`n-1`和`n-2`的加總，答案即為費氏數列。
* 稍微值得注意的點，我們得把已經算過的階梯給記錄起來，用以加速。

### Code

class Solution {
public:
    int table[100]={0};
    int Find(int f)
    {
        if(table[f]) return table[f];
        table[f] = Find(f-1)+Find(f-2);
        return table[f];
    }
    int climbStairs(int n) {
        table[1]=1;
        table[2]=2;
        table[3]=3;
        return Find(n);
    }
};

###### tags: `LeetCode` `C++`