LeetCode Js-70. Climbing Stairs

    AllenLi
    LeetCode Js-Optimization

    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;
};

    Related Posts