讓我們考慮使用動態規劃實現斐波那契數列。使用動態規劃的斐波那契數列
// 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));
}
}
我們使用動態編程,以便不會發生遞歸工作的重複。但是,在每次調用該函數時,都會生成一個新數組。那麼這個算法怎麼會被說成是更優化的呢?
每次? 。我猜這個數組會在每個函數調用中創建一次。假設你想找到第100個斐波納契數。所以一個100的數組將只創建一次來存儲數字。 – FallAndLearn
如果你不想在每次調用'fib'時創建數組,請不要在'fib'中創建它。 – zmbq
另外,添加遞歸函數也會在創建樹時使用O(n)空間。 – FallAndLearn