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