追根揭底-循环\迭代\分治详细使用

PayneWu

发布于 2020-12-18 10:33:46

60200

代码可运行

文章被收录于专栏：积跬Coder积跬Coder

运行总次数：0

代码可运行

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除

python