From 4d53fa14ee0cd615444aca6f6ba176e0ccc1b5be Mon Sep 17 00:00:00 2001
From: TheSiahxyz <164138827+TheSiahxyz@users.noreply.github.com>
Date: Mon, 29 Apr 2024 22:06:12 -0400
Subject: init

---
 SI/Resource/Dynamic Programming/fibonacci.py | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
 create mode 100644 SI/Resource/Dynamic Programming/fibonacci.py

(limited to 'SI/Resource/Dynamic Programming/fibonacci.py')

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
-- 
cgit v1.2.3