怎么做网站代码,电商网站开发教程,网站文章页要不要做内链,北京企业网站设计报价Multiple solutions of Fibonacci (Python or Java)本章是用英文写的#xff0c;作为或想成为一名优秀的攻城狮#xff0c;习惯阅读英文文档将使你受益良多。例如更好的查看最新版的官方文档、与国外友人交流、等等 其实英文的生词也并不多,其中90#xff05;的英文都在代码…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 Code1234class Solution:def fib(self, N: int) - int:if N 1 or N 2: return Nreturn self.fib(N - 1) self.fib(N - 2)Java Code123456789101112class 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 calculationPython Code12345class Solution2:functools.lru_cache()def fib(self, N: int) - int:if N 1: return Nelse: return self.fib(N - 1) self.fib(N - 2)Java Code1234567891011121314class 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 solutionRecursion, iteration, divide and conquer, backtracking, they do not have a clear distinction RecursionThe core idea is to govern separately and unify the officials1234567class Solution:def fib(self, N: int) - int:memo {}if N 2: return Nif 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 solutionsMore initial value, continuous dynamic recursivePython Code12345678910111213141516class Solution:def fib(self, N: int) - int:if N 2: return Ndp [0 for _ in range(N 1)]dp[0], dp[1] 0, 1for 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 0memo [0,1]for _ in range(2,N1):memo [memo[-1], memo[-1] memo[-2]]return memo[-1]Java Code12345678910111213class 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 performance1234567class Solution:def fib(self, N: int) - int:if N 0: return 0memo (0,1)for _ in range(2,N1):memo (memo[-1], memo[-1] memo[-2])return memo[-1]Better solutionsPython Code123456789101112131415class Solution:def fib(self, N: int) - int:curr, prev1, prev2 0, 1, 1for i in range(3, N 1):curr prev1 prev2prev2 prev1prev1 currreturn currclass Solution5:def fib(self, N: int) - int:prev, now 0, 1for i in range(N):prev, now now, now prevreturn prevJava Code12345678910111213class 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 methodPython Code12345class Solution:def fib(self, N: int) - int:sqrt5 5 ** 0.5fun pow((1 sqrt5) / 2, n 1) - pow((1 - sqrt5) / 2, n 1)return int(fun / sqrt5)Java Code123456class Solution {public int fib(int N) {double sqrt5 (1 Math.sqrt(5)) / 2;return (int)Math.round(Math.pow(sqrt5, N)/ Math.sqrt(5));}}
