Fibonacci数列的动态规划算法

来自计算思维百科
跳转至: 导航搜索

递归一节所讲的Fibonacci数列也可用动态规划自底向上递推计算。用一个数组F记录Fibonacci数列,初始F[1]=1,F[2]=1,然后根据式F[i]=F[i-1]+F[i-2]顺序计算F[3],…,F[n]。

动态规划求Fibonacci数列的伪代码描述如下:

Fibonacci数列的动态规划算法如下:

输入:正整数n

输出:Fibonacci数列的第n项

Fib(n)

1   F[1]ß F[2]ß1

2  FOR i=3 to n

3  DO   F[i] ß F[i-1]+F[i-2]

4  RETURN F[n]