@@ -18,7 +18,8 @@ public static void main(String[] args) throws Exception {
1818BufferedReader br =new BufferedReader (new InputStreamReader (System .in ));
1919int n =Integer .parseInt (br .readLine ());
2020
21- System .out .println (fib (n ));// Returns 8 for n = 6
21+ System .out .println (fibMemo (n ));// Returns 8 for n = 6
22+ System .out .println (fibBotUp (n ));// Returns 8 for n = 6
2223 }
2324
2425/**
@@ -28,7 +29,7 @@ public static void main(String[] args) throws Exception {
2829 * Outputs the nth fibonacci number
2930 **/
3031
31- public static int fib (int n ) {
32+ public static int fibMemo (int n ) {
3233if (map .containsKey (n )) {
3334return map .get (n );
3435 }
@@ -45,5 +46,30 @@ public static int fib(int n) {
4546
4647return f ;
4748 }
49+
50+ /**
51+ * This method finds the nth fibonacci number using bottom up
52+ *
53+ * @param n The input n for which we have to determine the fibonacci number
54+ * Outputs the nth fibonacci number
55+ **/
56+
57+ public static int fibBotUp (int n ) {
58+
59+ Map <Integer ,Integer >fib =new HashMap <Integer ,Integer >();
60+
61+ for (int i =1 ;i <n +1 ;i ++) {
62+ int f =1 ;
63+ if (i <=2 ) {
64+ f =1 ;
65+ }
66+ else {
67+ f =fib .get (i -1 ) +fib .get (i -2 );
68+ }
69+ fib .put (i ,f );
70+ }
71+
72+ return fib .get (n );
73+ }
4874}
4975