[70] Climbing Stairs

用遞迴寫會超時 囧
所以就是DP的精髓！（嗎XD）
費波那西數列(Fibonacci)
重點是前面算過的存起來給下一個用
就不用再算一次, 可以加速.

Climbing Stairs
int climbStairs(int n) {
    int ret=0;
    if (n==1)
        return 1;
    if(n==2)
        return 2;
    int f1,f2,f3;
    f1=1;
    f2=2;
    for(int i =3;i<=n;i++)
    {
        f3 = f1+f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

20220124更新：也可以用一整個array 存每個值

int climbStairs(int n){

int *stairs=calloc(45,sizeof(int));

stairs[0]=1; //n=1

stairs[1]=2; //n=2

for (int i=2;i<n;i++)

stairs[i]=stairs[i-1]+stairs[i-2];

return stairs[n-1];

}