每日一算 -- 斐波那契數列型別題
摘要：
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
日常找規律
當有1階時 F(1) = 1
當有2階時 F(2) = 2(可以1階或者2階)
當有3階時 F(...
假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數。
日常找規律
- 當有1階時 F(1) = 1
- 當有2階時 F(2) = 2(可以1階或者2階)
- 當有3階時 F(3) = 3(可以1階或者1、2階或者2、1)
- 當有4階時 F(4) = 5(可以1階或者1、2、1、1階或2、1、1、1或2、2、1或2、1、2)
- ...
- 當有n階時 F(n) = F(n - 1) + F(n - 2)
F(1)=1 F(2)=2 F(n)=F(n-1)+F(n-2) 複製程式碼
實現方式
當我們得到推導公式，實現函式腦海裡面會想到遞迴實現
遞迴
- 時間複雜度: O(2^n)
function fiber (n) {
if ( n === 1) {
return 1
}
if ( n === 2) {
return 2
}
return fiber( n - 1) + fiber( n - 2 )
}
複製程式碼
迴圈
- 時間複雜度: O(n)
- 空間複雜度: O(n)
function fiber (n) {
let step = []
step[0] = 1
if ( n >= 2) {
step[1] = 2
}
if ( n <= 2) {
return n
}
for ( let i = 2; i <= n; i++) {
step[i] =step[i - 1] + step[i - 2]
}
return step[n]
}
複製程式碼
迴圈 + 優化空間複雜度
- 時間複雜度: O(n)
- 空間複雜度: O(1)
function fiber (n) {
let prev1 = 1
let prev2 = 2
let result = 0
if ( n <= 2) {
return n
}
for ( let i = 2; i <= n; i++) {
result = prev1 + prev2
prev1 = prev2
prev2 = result
}
return result
}
複製程式碼