Calculate the fibonacci number at position n using dynamic programming to improve runtime
(n: int, fib: list)
| 37 | |
| 38 | |
| 39 | def getFibonacciDynamic(n: int, fib: list) -> int: |
| 40 | """ |
| 41 | Calculate the fibonacci number at position n using dynamic programming to improve runtime |
| 42 | """ |
| 43 | |
| 44 | if n == 0 or n == 1: |
| 45 | return n |
| 46 | if fib[n] != -1: |
| 47 | return fib[n] |
| 48 | fib[n] = getFibonacciDynamic(n - 1, fib) + getFibonacciDynamic(n - 2, fib) |
| 49 | return fib[n] |
| 50 | |
| 51 | |
| 52 | def main(): |