/ * *
The title
Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. That is:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2), where n > 1 gives you n, please calculate F(n).
Example 1:
Input: 2 Output: 1 Description: F(2) = F(1) + F(0) = 1 + 0 = 1 Example 2:
Input: 3 Output: 2 Description: F(3) = F(2) + F(1) = 1 + 1 = 2 Example 3:
Input: 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3
Tip:
0 <= n <= 30
Source: LeetCode link: leetcode-cn.com/problems/fi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
print(fib(4))
notes
There are four main ways to solve this problem
The first is recursion, as shown in code 1.1, but there are too many repetitions for pure recursion. You can use a dictionary to record the calculated data, as shown in code 1.2
The second method is dynamic programming, which computs from 2 bits to n. This method requires space to record the last value. The method of recording with a dictionary is described in code 2.1. The method of exchanging data after recording with an int is described in code 2.2
If 0 <= n <= 30, place the Fibonacci numbers in a dictionary and select the Fibonacci numbers directly, see code 3.1
The fourth is the general term formula, Fibonacci number has a general term formula calculation, directly set the formula, see code 4.1
The code address
Github.com/zmfflying/Z… * /
The problem solving code
Import Foundation // MARK: -1.1 //func fib(_ n: Int) -> Int { // if n < 2 { // return n // } // return fib(n - 1) + fib(n - 2) //} // MARK: // var dic: [Int: Int] = [Int: Int]() // //func help(_ n: Int) -> Int { // if let res = dic[n] { // return res // } // // if n < 2 { // return n // } // // let res = help(n - 1) + help(n-2) // dic[n] = res // return help(n) //} // MARK: Var dic: [Int: Int] = [Int:] var dic: [Int:] = [Int:] var dic: [Int:] = [Int:] Int () dic[0] = 0 dic[1] = 1 var I = 2 while I <= n { Sum = dic[i-1] = dic[i-1]! + dic[i - 2]! dic[i] = sum i += 1 } return dic[n]! } // MARK: -2.2 dynamic programming - data exchange //func fib(_ n: Int) -> Int {// if n < 2 {// return n //} // // // start from 2 // var pre = 0 // var cur = 1 // // var I = 2 // while I <= N {// // calculate the sum of this time, // sum = pre + cur // pre = cur // cur = sum // I += 1 // 3.1 lookup table / / func fib (_ n: Int) - > Int {/ / let dic: [Int: Int] = [0:0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 5, 6, 8, 7, 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040] // return dic[n]! Int Int (_ n: Int) -> Int {// let sqrt5: Double = sqrt(5) // let fibN = pow((1 + sqrt5) / 2, Double(n)) - pow((1 - sqrt5) / 2, Double(n)) // return Int(round(fibN / sqrt5)) //}Copy the code