Multiple solutions of Fibonacci(Python or Java)
Violence law(Top-down)
It can be solved directly according to the known conditions
(f (0) = 0, f (1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1)
Python Code
class Solution: def fib(self, N: int) -> int: if N == 1 or N == 2: return N return self.fib(N - 1) + self.fib(N - 2)
Java Code
class Solution { public int fib(int N) { if (N == 1 || N == 2) return 1; return fib(N - 1) + fib(N - 2); } }class Solution { public int fib(int N) { return N < 2 ? N : fib(N - 1) + fib(N - 2); } }
Violence law add cache(Pruning)
We know that if we don’t do any processing, we will repeat too many
calculations, which is very bad
The processing idea will avoid repeated calculation
Python Code
class Solution2: @functools.lru_cache() def fib(self, N: int) -> int: if N <= 1: return N else: return self.fib(N - 1) + self.fib(N - 2)
Java Code
class Solution { private Integer[] cache = new Integer[31]; public int fib(int N) { if (N <= 1) return N; cache[0] = 0; cache[1] = 1; return memoize(N); } public int memoize(int N) { if (cache[N] != null) return cache[N]; cache[N] = memoize(N-1) + memoize(N-2); return memoize(N); } }
Divide and conquer solution
Recursion, iteration, divide and conquer, backtracking, they do not have a clear distinction
Recursion：The core idea is to govern separately and unify the officials
class Solution: def fib(self, N: int) -> int: memo = {} if N < 2: return N if N-1 not in memo: memo[N-1] = self.fib(N-1) if N-2 not in memo: memo[N-2] = self.fib(N-2) return memo[N-1] + memo[N-2]
Dynamic recursion(Bottom up)
Basic solutions
More initial value, continuous dynamic recursive
Python Code
class Solution: def fib(self, N: int) -> int: if N < 2: return N dp = [0 for _ in range(N + 1)] dp[0], dp[1] = 0, 1 for i in range(2, N + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[- 1]class Solution: def fib(self, N: int) -> int: if N == 0: return 0 memo = [0,1] for _ in range(2,N+1): memo = [memo[-1], memo[-1] + memo[-2]] return memo[-1]
Java Code
class Solution { public int fib(int N) { if (N <= 1) return N; if (N == 2) return 1; int curr = 0, prev1 = 1, prev2 = 1; for (int i = 3; i <= N; i++) { curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return curr; } }
Use better base types (tuples) to improve performance
class Solution: def fib(self, N: int) -> int: if N == 0: return 0 memo = (0,1) for _ in range(2,N+1): memo = (memo[-1], memo[-1] + memo[-2]) return memo[-1]
Better solutions
Python Code
class Solution: def fib(self, N: int) -> int: curr, prev1, prev2 = 0, 1, 1 for i in range(3, N + 1): curr = prev1 + prev2 prev2 = prev1 prev1 = curr return currclass Solution5: def fib(self, N: int) -> int: prev, now = 0, 1 for i in range(N): prev, now = now, now + prev return prev
Java Code
class Solution { public int fib(int N) { if (N == 0) return 0; if (N == 2 || N == 1) return 1; int prev = 1, curr = 1; for (int i = 3; i <= N; i++) { int sum = prev + curr; prev = curr; curr = sum; } return curr; } }
Mathematical conclusion method
Python Code
class Solution: def fib(self, N: int) -> int: sqrt5 = 5 ** 0.5 fun = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1) return int(fun / sqrt5)
Java Code
class Solution { public int fib(int N) { double sqrt5 = (1 + Math.sqrt(5)) / 2; return (int)Math.round(Math.pow(sqrt5, N)/ Math.sqrt(5)); } }
