什么是动态规划？

• 2022 年 8 月 28 日
• 筆記
• 动态规划, 算法设计与分析Java

• 什么是动态规划？

今天简单说一下动态规划的定义以及简单示例。动态规划，是一种将原问题分解成简单的子问题来解决复杂问题的思想。

其中，动态规划还具有最优子结构性质和子问题重叠性质。

最优子结构：动态规划将原问题分解成各种简单的子问题时，各个子问题的最优解综合起来就是原问题的最优解，即局部最优解能够决定全局最优解。

子问题重叠：在计算一个子问题的最优解之后，记住这个子问题，接下来还可能遇到相同问题，为提高效率，可以直接拿来之前得到的结果，这是因为当使用递归自顶向下的时候，每次产生的子问题不总是新问题，而是之前被重复计算的问题。

• 斐波那契数列

接下来简单利用斐波那契数列来介绍一下动态规划：

斐波那契数列：0，1，1，2，3，5，8，13，21，34，55，89、、、、、、规律是从第三项开始，每一项都等于前两项之和，F(n)=F(n-1)+F(n-2),(n>=3)

问题简单描述：

给一个整型数值n，输出斐波那契数列中对应的第n项数值

在不了解动态规划地情况下，我们一般都是利用普通递归来解决

1 public int fabocci(int n){
2     if(n<1)
3         return 0;
4     else if(n==1)
5         return 1;
6     else if(n==2)
7         return 1;
8     return fabocci(n-1)+fabocci(n-2);
9 }

显然每次调用fabocci函数时，因为第三项之后都是前两项之和，所以会出现大量的重复计算，且时间复杂度为O(2^n)

基于相邻两项之和可以推出下一项，于是可以采用自底向上的方法：

 1 public int fabocci(int n){
 2     if(n<1)
 3         return 0;
 4     else if(n==1)
 5         return 1;
 6     else if(n==2)
 7         return 1;
 8 //temp1,temp2既是相邻两项的值，也是为了记录迭代出来的结果，方便下一次计算使用
 9     int temp1=1;
10     int temp2=1;
11     int temp=0;
12     for(int i=3;i<=n;i++){
13         temp=temp1+temp2;
14         temp1=temp2;
15         temp2=temp;
16     }
17     return temp;
18 }

以上仅以学习记录，如有问题，请及时指正，我们共同进步，谢谢！