Week2 Python Fibonacci done!

1 files changed, 20 insertions, 0 deletions

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibonacci.py b/AlgoDesignAndTechniqueEdxPython/sources/fibonacci.py
new file mode 100644
index 0000000..debfb9e
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibonacci.py
@@ -0,0 +1,20 @@
+# Uses python3
+def calc_naive(n):
+    if (n <= 1):
+        return n
+ 
+    return calc_naive(n - 1) + calc_naive(n - 2)
+
+def calc_optimize1(n):
+    if (n <= 1):
+        return n
+    fibLst = [None] * (n+1)
+    fibLst[0] = 0
+    fibLst[1] = 1
+    for j in range(2, n+1):
+        fibLst[j] = fibLst[j-1] + fibLst[j-2]
+    return fibLst[n]
+
+n = int(input())
+print(calc_optimize1(n))
+