 JavaStudent - 4 years ago 63
Java Question

# Memoization of Dynamic Programming

I'm trying to learn Memoization of Dynamic Programming and I was watching video on youtube from MIT trying to follow along with it. I don't know how to compare the Nth value to an array.

``````int[] memo;
public int fib(int n) {
int f = 0;

if n is in memo then return memo[n] <----not sure how to code this line.

if (n<=2) {
f = 1;
} else {
f = fib(n-1) + fib(n-2);
}

memo[n] = f;
return f;
}
`````` Dukeling
Answer Source

Doing it with `ArrayList`:

``````ArrayList<Integer> memo = new ArrayList<Integer>();

public int fib(int n) {
if (memo.size() == 0)
memo.add(0); // element 0 is never accessed
fib2(n);
}

private int fib2(int n) {
int f = 0;

if (n < memo.size())
return memo.get(n);

if (n<=2) {
f = 1;
} else {
f = fib2(n-2) + fib2(n-1);
}

memo.add(f); // elements inserted in order
return f;
}
``````

Doing it with array:

``````int[] memo;

public int fib(int n) {
memo = new int[n]; // all initialized to 0
fib2(n);
}

private int fib2(int n) {
int f = 0;

if (memo[n] != 0)
return memo[n];

if (n<=2) {
f = 1;
} else {
f = fib2(n-2) + fib2(n-1);
}

memo[n] = f;
return f;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download