Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit35b17aa

Browse files
Merge pull requestTheAlgorithms#90 from varunu28/master
Added Fibanacci using memoization
2 parents1ac59ac +73e0594 commit35b17aa

File tree

1 file changed

+75
-0
lines changed

1 file changed

+75
-0
lines changed

‎Dynamic Programming/Fibonacci.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
importjava.io.BufferedReader;
2+
importjava.io.InputStreamReader;
3+
importjava.util.HashMap;
4+
importjava.util.Map;
5+
6+
/**
7+
*
8+
* @author Varun Upadhyay (https://github.com/varunu28)
9+
*
10+
*/
11+
12+
publicclassFibonacci {
13+
14+
publicstaticMap<Integer,Integer>map =newHashMap<Integer,Integer>();
15+
16+
publicstaticvoidmain(String[]args)throwsException {
17+
18+
BufferedReaderbr =newBufferedReader(newInputStreamReader(System.in));
19+
intn =Integer.parseInt(br.readLine());
20+
21+
System.out.println(fibMemo(n));// Returns 8 for n = 6
22+
System.out.println(fibBotUp(n));// Returns 8 for n = 6
23+
}
24+
25+
/**
26+
* This method finds the nth fibonacci number using memoization technique
27+
*
28+
* @param n The input n for which we have to determine the fibonacci number
29+
* Outputs the nth fibonacci number
30+
**/
31+
32+
publicstaticintfibMemo(intn) {
33+
if (map.containsKey(n)) {
34+
returnmap.get(n);
35+
}
36+
37+
intf;
38+
39+
if (n <=2) {
40+
f =1;
41+
}
42+
else {
43+
f =fib(n-1) +fib(n-2);
44+
map.put(n,f);
45+
}
46+
47+
returnf;
48+
}
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+
publicstaticintfibBotUp(intn) {
58+
59+
Map<Integer,Integer>fib =newHashMap<Integer,Integer>();
60+
61+
for (inti=1;i<n+1;i++) {
62+
intf =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+
returnfib.get(n);
73+
}
74+
}
75+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp