动态规划问题--斐波那契数列

﹏ヽ暗。殇╰゛Y 2023-01-19 14:56 184阅读 0赞

# 动态规划问题--斐波那契数列 #

**1** **斐波那契数列**

斐波那契数列其表达式如下：

![20210510233712765.png][]

**2** **递归算法**

通过公式我们不难看出，其第一项和第二项为1，当x>=3时，斐波那契数列的第x项就等于其前两项的和。所以我们可以得出代码如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:414.8pt;"> <p style="margin-left:0cm;">public static Integer fib(int n){ <br> &nbsp;&nbsp;&nbsp; if (n==1 || n==2){ <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 1;<br> &nbsp;&nbsp;&nbsp; }<br><br> &nbsp;&nbsp;&nbsp; return <em>fib</em>(n-2)+<em>fib</em>(n-1);<br> }</p> </td> 
  </tr> 
 </tbody> 
</table>

递归算法是自上而下的算法，要得出后面的值就得知道前两项的值，这样会产生大量重复计算，比如要求第七项的值，就需要知道第六项和第五项的值，要求第六项的值，就需要第五项和第四项的值，光这里就求了两次第五项的值，所以这种算法的效率不是很高。

**3** **动态规划算法**

在使用递归时，我们看到了递归的不足，因为其存在大量重复函数的调用，效率很低。我们可以试试动态规划，通过保存前两项的值来求解第x项的值。其代码如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:414.8pt;"> <pre style="margin-left:0cm;">public static Integer dp(int n){

&nbsp;&nbsp;&nbsp; int[] dp = new int[n+1];

&nbsp;&nbsp;&nbsp; dp[1] = 1;

&nbsp;&nbsp;&nbsp; dp[2] = 1;

&nbsp;&nbsp;&nbsp; for (int i = 3; i &lt;= n; i++) {

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; dp[i] = dp[i-1] + dp[i-2];

&nbsp;&nbsp;&nbsp; }

&nbsp;&nbsp;&nbsp; return dp[n];

}</pre> </td> 
  </tr> 
 </tbody> 
</table>