You are climbing a staircase. It takes n steps to reach the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

    你正在爬樓梯,需要幾步才到最上方。
    每次你可以選擇爬1步或2步,你可以有幾個方式爬到最上方呢?
    

    Example 1:

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

    Example 2:

    Input: n = 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:

    1. 先獨立出 n <= 1的情況
    2. 宣告 [one, two] = [1, 1]
    //分別是各一個步驟(one = 1次1階梯, two = 1次2階梯)
    3. 宣告 i = 2 ,兩種步驟
    4. 設立「For迴圈」
    temp = 紀錄上個one的可行步驟
    one = one(上上次的步驟)
          +
          two(上次的步驟)
    two = 紀錄這次temp的可行步驟
    ex. 每一次的迴圈代表前兩組的步驟相加,因為順序不同仍須計算為一次步驟
    

    Code 1: BigO(n)

    var climbStairs = function(n: number): number {
      if (n <= 1) return 1;
      if (n === 2) return 2;
    
      let newArray: number[] = [0, 1, 2]
      for (let i = 3; i <= n; i++) {
          newArray[i] = newArray[i - 2] + newArray[i - 1]
      }
      return newArray[n];
    };
    

    FlowChart:
    Example 1

    Input = 2
    (i = 2; i < = 2; i++)
    
    case1 => i = 1, steps = 1 (1次1階梯)
    case2 => i = 2, steps = 1 + 1 = 2 (1次1階梯 + 1次2階梯)
    
    return one = 2
    

    Example 2

    Input = 3
    (i = 2; i < = 3; i++)
    
    case1 => i = 1, steps = 1 (1次1階梯)
    case2 => i = 2, steps = 1 + 1 = 2 (1次1階梯 + 1次2階梯)
    case2 => i = 3, steps = 1 + 2 = 3 (case1 + case2)
    
    return one = 3
    

    Code 2: BigO(n)

    var climbStairs = function(n: number): number {
        if (n <= 1) return 1 
        if (n === 2) return 2
    
        let [one, two]: [number, number] = [1, 1]    
        for (let i = 2; i <= n; i++) {
            let temp = one
            one = one + two
            two = temp
        }
        return one;
    };