---
title: 2023 年資訊科技產業專案設計作業二
tags: INF02023
---

# 2023 年資訊科技專案設計作業二
> 作者: 東尼-Tonny
> 影片左邊：Interviewee
> 影片右邊：Interviewer

### 作業檢討
#### 優點：
蠻多同學的影片都蠻流暢的，能夠做到邊寫Code邊講解。
還有畫圖解釋作法的，這個我也覺得還不錯。
#### 可以改善的地方：
有些同學的影片中沒有完全做到REACTO的所有步驟。
像是Test，有些同學沒有做到測試就結束。
還有面試雙方的互動太少之類的。
#### 學到甚麼：
我覺得自己要多練習描述想法，寫Code的速度也要再練。
要多練習自言自語。

### [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
>[video](https://youtu.be/R-71LKUt_Bc)

### 題目敘述
你正在爬樓梯。需要n個步驟才能到達頂部。
每次你可以向上爬一步或兩步。你有多少種不同的方式可以爬到頂部？

### 程式碼解說

#### 方法一: ***遞迴求解***
使用遞迴的方式求解，初始狀態是`n = 0`或`n = 1`
其他狀況則是呼叫`climbStairs(n-1) + climbStairs(n-2)`求值。
這個做法由於要重覆計算先前已經算過的值，不是好的做法
時間複雜度為：`O(2^n)`，`n`為總步驟數目。

class Solution {
public:
    int climbStairs(int n) {
        if(n == 0 || n == 1){
            return 1;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

#### 方法二: ***Dynamic Programming***
使用Dynamic Programming的方式求解，先建立一個陣列`dp`紀錄先前計算過的結果。
初始狀態是`n = 0`或`n = 1`
其他狀況則使用`dp[i] = dp[i-1] + dp[i-2]`求值。
這個做法改善了要重覆計算，呼叫函式的問題，比前面那個作法好。
在時間方面只需要對陣列做一次尋訪即可求出結果。
時間複雜度為：`O(n)`，`n`為總步驟數目。
空間複雜度則是因為要用到`n`格陣列空間，為`O(n)`。

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        vector<int> dp(n+1);
        dp[0] = dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

### 面試過程檢討

#### **Interviewer**

自評：要多問面試者一些問題，不要就放著讓面試者一直自己講，要試著打斷他。

#### **Interviewee**

自評：對自己的想法的描述要清楚一點，打字速度要練習，現在這樣太慢。
要試著多加一些自己的開發經驗到解題過程中。
聲音可以再大聲一點。