CODEWITHSUNDEEP
javarecursiondynamic-programmingfibonacci
Zeus
Zeus

Reputation: 2253

Fibonacci using Dynamic programming

I'm trying to code a slightly modified Fibonacci.

Here n = (n-1)^2 + (n-2)

Here's my code,

public static int fibonacci(int first, int second, int n){
    int[] memo = new int[n + 1];
    for(int i=0; i<= n; i++){
        memo[i] = -1;
    }
    return fibonacci(first, second, n, memo);

}

public static int fibonacci(int first, int second, int n, int[] memo){
    if(n == first || n == second) return n;

    if(memo[n] < 0) memo[n] =  (int)Math.pow(fibonacci(first, second, n-1, memo), 2) + fibonacci(first, second, n-2, memo);

    return memo[n];
}

I've tried debugging it several times over, but can't seem to figure out where the problem is. This code yields the next number, thus it yields F(6) for F(5). Any help appreciated. Please understand, I can solve this problem interactively, but that's not what I'm trying to do. I want to do it using this DP approach.

Upvotes: 1

Views: 560

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

You have a logic error in your code.

first and second is the value of the first and second terms in your sequence, and n is the index of value you want to find. But here, you compare index and value, which is wrong: 

    if(n == first){
        return memo[n] = first;

    }
    if(n == second) return memo[n] = second;

It should be:

    if(n == 1){
        return memo[n] = first;

    }
    if(n == 2) return memo[n] = second;

Upvotes: 2

Related Questions