Multiple solutions of Fibonacci (Python or Java)

本章是用英文寫的，作為或想成為一名優秀的攻城獅，習慣閱讀英文文檔將使你受益良多。例如更好的查看最新版的官方文檔、與國外友人交流、等等 其實英文的生詞也并不多,其中90％的英文都在代碼里，當然這其中的精華也在代碼里，代碼相信大部分伙計還是都可以看懂.所以，請不要驚慌。對于English，讓我們一起取克服它、習慣它、擁抱它。然后把它錘倒在地，相信你可以的。 GO， Go， GO 如果實在不行，各種頁面翻譯來一手。莫慌，這都是小場面，啥都不是事兒，好吧

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

1

2

3

4

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

1

2

3

4

5

6

7

8

9

10

11

12

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

1

2

3

4

5

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

1

2

3

4

5

6

7

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

1

2

3

4

5

6

7

8

9

10

11

12

13

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

1

2

3

4

5

6

7

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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 curr

class 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

1

2

3

4

5

6

7

8

9

10

11

12

13

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

1

2

3

4

5

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

1

2

3

4

5

6

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

}

}