The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
運用費波那契數來表示 F(n),使每個數為前兩個數的合,從 0 和 1 開始: F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 給予 n 來計算 F(n) 的結果。
Example 1:
Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Solution:
1. 判斷 f(0) = 0 為 0, f(1) = 1 為 1。
2. 每一輪的 f(n) 套入 fib function 拆分為 f(1) 與 f(0) 的組合後進行加總。
Code.1:
var fib = function(n) { if (n <= 0) { return 0 } else if (n === 1) { return 1 } else { return fib(n - 1) + fib(n - 2) } }
FlowChart:
Example 1
Input: n = 2 fib(2 - 1) = fib(1) = 1 fib(2 - 2) = fib(0) = 0 return fib(1) + fib(0) = 1
Example 2
Input: n = 3 fib(3 - 1) = fib(2) => fib(2 - 1) = fib(1) = 1 fib(3 - 2) = fib(1) = 1 return fib(2) + fib(1) = 1 + 1 = 2
Example 3
Input: n = 4 fib(4 - 1) = fib(3) => fib(2) + fib(1) => (fib(1) + fib(0)) + fib(1) => 1 + 1 = 2 fib(4 - 2) = fib(2) => fib(1) + fib(0) = 1 return fib(3) + fib(2) => 2 + 1 = 3
Code.2: dp
var fib = function(n) { let dp = [0, 1]; for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; };