java优化递归斐波那契方法。

Question

我正在尝试优化斐波那契递归方法，这样它就不会像递归方法那样慢。这些方法的参数必须如此。无论何时我运行它，它都不会给我所需的结果。任何关于如何前进的建议都会有所帮助

      public static long optimizedFib(int n)
      {
          long[] parameters = new long[3];
          for(int i =0; i < n;i++)
          {
             parameters[i] = 1;
          }
          return optimizedFib(n, parameters);
      }

public static long optimizedFib(int n, long[] parameters)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {   
    parameters[2] = parameters[1] + parameters[0];
    parameters[1] = parameters[0]; 
    parameters[0] = parameters[2];
    }
    return optimizedFib(n-1, parameters);
}

}

Answer 1

首先，您正在吹过数组的边界。您可以定义大小为3的数组：

long[] parameters = new long[3];

然后迭代到n

for(int i =0; i < n;i++)
{
    parameters[i] = 1;
}

您还将值初始化为1，这是不正确的。由于您只使用三个索引，并且我们只需要第一个索引为1，因此我们可以简单地将第一个索引初始化为1（其余的值将默认为0）

public static long optimizedFib(int n)
{
    long[] parameters = new long[3];
    parameters[0]=1;
    return optimizedFib(n, parameters);
}

接下来，递归方法从未返回计算结果（它只返回1）。为了解决这个问题，我们递归调用optimizedFib，然后返回parameters[0]和parameters[1]之和

public static long optimizedFib(int n, long[] parameters)
{
    if(n <= 0){
        return 0;
    }
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        parameters[2] = parameters[1] + parameters[0];
        parameters[1] = parameters[0];
        parameters[0] = parameters[2];
        optimizedFib(n-1, parameters);
        return parameters[0] + parameters[1];
    }
}

注意n > 92时long数据类型将溢出

补充资料

这种优化称为Memoization。您可以看到更多的实现here。在我看来，有一个迭代解决方案更容易探索：

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    int[] f = new int[n+1];
    f[0] = 0;
    f[1] = 1;
    for(int i = 2;i<=n;i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

Source