Фибоначчи с использованием динамического программирования

Question

Я пытаюсь закодировать слегка модифицированный Фибоначчи.

n = (n-1)^2 + (n-2) Здесь

Вот мой код,

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

Я пытался отладки его в несколько раз, но не могу показаться, чтобы выяснить, где проблема. Этот код дает следующее число, поэтому он дает F (6) для F (5). Любая помощь оценивается. Пожалуйста, поймите, я могу решить эту проблему в интерактивном режиме, но это не то, что я пытаюсь сделать. Я хочу сделать это, используя этот подход DP.

Answer 1

У вас есть логическая ошибка в коде.

first и second - это значение первого и второго условий в вашей последовательности, а n - это индекс значения, который вы хотите найти. Но здесь, вы сравниваете индекс и значение, которое является неправильным:

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

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

Оно должно быть:

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

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