# Leetcode 70. Climbing Stairs (C語言)
- 題目
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?
- 範例
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

int climbStairs(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    int* arr=(int*)malloc((n)*sizeof(int));
    arr[0]=1;
    arr[1]=2;
    int i;
    for(i=2;i<n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1];
}

思路:第n階樓梯怎麼爬上來? ans:從n-1階爬一層或者從n-2階爬兩層
=> arr[n]=arr[n-1]+arr[n-2]

題外話:此題即費伯那西數列。