algorithm - 使用动态规划的斐波那契数列

Question

让我们考虑使用动态规划实现斐波那契数列。

// Fibonacci Series using Dynamic Programming
class fibonacci
{
static int fib(int n)
{
    /* Declare an array to store Fibonacci numbers. */
int f[] = new int[n+1];
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
   /* Add the previous 2 numbers in the series
     and store it */
    f[i] = f[i-1] + f[i-2];
}

return f[n];
}

public static void main (String args[])
{
    int n = 9;
    System.out.println(fib(n));
}
} 

我们使用动态规划，这样递归工作就不会重复发生。但是这里每次调用该函数时，都会生成一个新数组。那么这个算法怎么能说是更优化呢？

Answer 1

一个优化是只保存最后 2 个值而不是所有结果。您不需要存储所有结果。

您还可以在 O(n) 中递归地编写斐波那契数列:

int fib(int n1, int n2, int counter)
{
    if(counter == 0)
    {
        return n2;
    }
    else
    {
        return fib(n2,n2 + n1,counter-1);
    }
}

//to start:
int result = fib(0,1,100); //gives you the 100 fibonacci value

这段代码递归运行并且易于阅读。您不必初始化数组或其他东西。

或者，您可以使用非递归选项:

int fib(int number)
{
    int n1 = 0;
    int n2 = 1;
    int temp;
    for(int i = 0; i< number;i++)
    {
        temp = n1 + n2;
        n1 = n2;
        n2 = temp;
    }
    return n2;
}

如果你想存储你的结果，你必须在你的 fib 函数之外初始化数组:

// Fibonacci Series using Dynamic Programming
class fibonacci
{
    /* Declare an array to store Fibonacci numbers. */
    int f[];

    static void init(int n)
    {    /* 0th and 1st number of the series are 0 and 1*/
        f = new int[n+1];            
        f[0] = 0;
        f[1] = 1;
    }

    static int fib(int n)
    {
        int i;

        for (i = 2; i <= n; i++)
        {
           /* Add the previous 2 numbers in the series
             and store it */
            f[i] = f[i-1] + f[i-2];
        }

        return f[n];
    }

    public static void main (String args[])
    {
        int n = 9;
        init(n);
        System.out.println(fib(n));
    }
}