[Algorithm] Fibonacci problem by using Dynamic programming
vThere are three ways to solve Fibonacci problem
- Recursion
- Memoize
- Bottom-up
'First Recursion approach:
def fib(n): if n == 1 or n == 2: result = 1 else: result = fib(n-1) + fib(n -2) return result;
As we can see to calculate fib(5), we need to calculate fib(3) twice and fib(2) three times.
Time complexity is O(2^n), because for each n from 3, we need to call fib() twice in else block:
else: result = fib(n-1) + fib(n -2)
To solve the problem, we can use memoize solution to solve repeated calculation.
deb fib(n, memo): if memo[n] != null return memo[n] if n == 1 or n == 2: result = 1 else: result = fib(n - 1) + fib(n-2) memo[n] = result return result
Using fib(5) as example: to calulate fib(5) we need to know fib(4)..fib(3), fib(2), fib(1), since we already know fib(1), fib(2) = 1, then we can know fib(3) = 2..fib(4) = 3, fib(5) = 5.
Time complexity is O(2n + 1) -> O(n): because we just need to go though memo once. And 2*2 is because of:
result = fib(n - 1) + fib(n-2)
We still can improve it by using bottom up approach, because from the previous solution:
Using fib(5) as example: to calulate fib(5) we need to know fib(4)..fib(3), fib(2), fib(1), since we already know fib(1), fib(2) = 1, then we can know fib(3) = 2..fib(4) = 3, fib(5) = 5.
We can clear see the solution the problem by going from bottom (fib(1) & fib(2)) to up (fib(5)):
def fib_bottom_up(n): if n == 1 or n == 2: return 1 bottom_up = new int[n+1] bottom_up[1] = 1 bottom_up[2] = 1 for i from 3 upto n: bottom_up[i] = bottom_up[i-1]+bottom_up[i-2] return bottom_up[n]
Time complexity is O(n).
Notice that some programming language has recursion limit, for example, python has set the limiation to 1000, which mean if you keep calling one function 1000 times, it will throw errors.
In this sense, bottom up is much better than recursion apporach (recursion and memoize).
相关文章
- [Javascript] Destructuring array by using object syntax
- [Functional Programming] Find max / min value by using Ramda
- [Vue] Lazy Load a Route by using the Dynamic Import in Vue.js
- [PWA] Check Online Status by using the NavigatorOnLine API
- [Tools] Create your own mobile emulator device by using Chrome dev tool
- [Javascript] Refactoring: Array.prototype by example [filter, some, forEach]
- 去掉WARN spring.jpa.open-in-view is enabled by default
- [Javascript] Create 2d array by using Array.from
- [Typescript] Key remapping in mapped types by using `as` keyword V4.2
- [Functional Programming] Find max / min value by using Ramda
- [RxJS] Remember previous value by using pairwise operator
- [ARIA] Group different DOM element in screen reader by using aria-labelledby
- [React] Preventing extra re-rendering with function component by using React.memo and useCallback
- [Vue] Lazy Load a Route by using the Dynamic Import in Vue.js
- [Tools] Create your own mobile emulator device by using Chrome dev tool
- [TypeScript] Shallow copy object by using spread opreator
- FreeSWITCH G.729 module using the opensource bcg729 implementation by Belledonne Communications
- Gcexcel for java 5.0.3 By Xacker
- 成功解决Type Error: can‘t multiply sequence by non-int of type ‘float‘
- SQL学习之使用order by 依照指定顺序排序或自己定义顺序排序
- QAxBase: Error calling IDispatch member Open: Exception thrown by server
- Must Know Tips/Tricks in Deep Neural Networks (by Xiu-Shen Wei)
- Warning: (3719, “‘utf8’ is currently an alias for the character set UTF8MB3, which will be replaced by UTF8MB4 in a future release. Please consider using UTF8MB4 in order to be unambiguous.”)
- (SRNTT)Image Super-Resolution by Neural Texture Transfer