JavaStudent 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;
}

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