init

1 files changed, 17 insertions, 0 deletions

diff --git a/SI/Resource/Dynamic Programming/fibonacci.py b/SI/Resource/Dynamic Programming/fibonacci.py
new file mode 100644
index 0000000..9c6b4fd
--- /dev/null
+++ b/SI/Resource/Dynamic Programming/fibonacci.py
@@ -0,0 +1,17 @@
+# fibonacci
+# time complexity: O(n^2)
+# space complexity: O(n)
+def fib(n):
+    return 1 if n <= 2 else fib(n - 1) + fib(n - 2)
+
+
+# memoization
+# time complexity: O(n)
+# space complexity: O(n)
+def fib_memo(n, memo={}):
+    if n <= 2:
+        return 1
+    if n in memo:
+        result = memo[n]
+    result = fib_memo(n - 1, memo[n]) + fib_memo(n - 2, memo[n])
+    return result