# 作業 2 遞精喔
### 題目:請【至少】使用 3 種方法來解[Leetcode_climbing_stairs](https://leetcode.com/problems/climbing-stairs/)
---
## 解法
### 主程式
主要就是把變數stair導到不同的解法函式中，最後在印出結果。
以下為程式碼

#include <stdio.h>
int climbStairs(int n);

int main(void)
{
    int stair = 0;
    while (scanf("%d", &stair) != EOF)
    {
        printf("%d\n", climbStairs(stair));
    }
}

---

### 1.一般遞迴
類似於費波那契數列 [F(n) = F(n - 1) + F(n - 2)]
簡單明瞭，但是太耗費記憶體，容易TLE。
以下為程式碼

int climbStairs(int n)
{
    if (n < 0)
        return 0;
    if (n == 1 || n == 0)
        return 1;
    else
    {
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

### Leetcode結果: TLE

---
### 2.遞迴記憶
開一個陣列step[46] = {0};
題目設定範圍為 1 <= n <= 45
使用此方法避免重複計算
以下為程式碼

int climbStairs(int n)
{
    int step[46] = {0};
    for (int i = 0; i < n; i++)
    {
        if (i == 0 || i == 1 || i == 2)
        {
            step[i] = i;
        }
        else
        {
            step[i] = step[i - 1] + step[i - 2];
        }
    }
    return step[n];
}

### Leetcode結果: AC

Runtime: 0ms
Memory: 5.4MB

---
### 3.使用For迴圈
我認為是比較簡單好懂的一種方法，與前面一種方法耗費記憶體量差不多。
以下為程式碼

int climbStairs(int n)
{
    int i = 0, j = 0;
    int answer = 0;
    if (n < 0)
    {
        return 0;
    }
    else if (n == 0 || n == 1)
    {
        return 1;
    }
    else if (n == 2)
    {
        return 2;
    }
    i = 1, j = 2;
    for (int k = 2; k < n; k++)
    {
        answer = i + j;
        i = j;
        j = answer;
    }
    return answer;
}

### Leetcode結果: AC

Runtime: 0ms
Memory: 5.4MB

---
### 結果比較

| | 一般遞迴 | 遞迴記憶 | for迴圈 |
| -------- |:-------- |:-------- |:------- |
| 記憶體 | Unknown | 5.4MB | 5.4MB |
| 執行速度 | TLE | 0 ms | 0 ms |

---
### 程式連結
1.[一般遞迴](https://replit.com/@SamuelTsai/HWrecursion1#main.c)
2.[遞迴記憶](https://replit.com/@SamuelTsai/HWrecursion2#main.c)
3.[For迴圈](https://replit.com/@SamuelTsai/HWrecursion3#main.c)