Merge pull request TheAlgorithms#649 from shoaibrayeen/patch-1

yanglbme · web-flow · commit 6218de047e2e · 2018-11-26T08:51:18.000+08:00
Optimized Version  [Without Hashmap &amp; recursion]
diff --git a/Dynamic Programming/Fibonacci.java b/Dynamic Programming/Fibonacci.java
@@ -29,6 +29,10 @@ public static void main(String[] args) throws Exception {
      * Outputs the nth fibonacci number
      **/
 
+    
+   
+    
+    
     private static int fibMemo(int n) {
         if (map.containsKey(n)) {
             return map.get(n);
@@ -71,5 +75,35 @@ private static int fibBotUp(int n) {
 
         return fib.get(n);
     }
+    
+    
+    
+    /**
+     * This method finds the nth fibonacci number using bottom up
+     *
+     * @author Shoaib Rayeen (https://github.com/shoaibrayeen)
+     * @param n The input n for which we have to determine the fibonacci number
+     * Outputs the nth fibonacci number
+     * 
+     * This is optimized version of Fibonacci Program. Without using Hashmap and recursion.
+     * It saves both memory and time.
+     *  Space Complexity will be O(1)
+     *  Time Complexity will be O(n)
+     *
+     *  Whereas , the above functions will take O(n) Space.
+     **/
+    private static int fibOptimized(int n) {
+ 
+        if (n == 0) {
+            return 0;
+        }
+        int prev = 0 , res = 1 , next;
+        for ( int i = 2; i < n; i++) {
+              next = prev + res;
+              prev = res;
+              res = next;
+        }
+        return res;
+    }
 }
 
