- 什么是动态规划?
今天简单说一下动态规划的定义以及简单示例。动态规划,是一种将原问题分解成简单的子问题来解决复杂问题的思想。
其中,动态规划还具有最优子结构性质和子问题重叠性质。
最优子结构:动态规划将原问题分解成各种简单的子问题时,各个子问题的最优解综合起来就是原问题的最优解,即局部最优解能够决定全局最优解。
子问题重叠:在计算一个子问题的最优解之后,记住这个子问题,接下来还可能遇到相同问题,为提高效率,可以直接拿来之前得到的结果,这是因为当使用递归自顶向下的时候,每次产生的子问题不总是新问题,而是之前被重复计算的问题。
- 斐波那契数列
接下来简单利用斐波那契数列来介绍一下动态规划:
斐波那契数列: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 }
以上仅以学习记录,如有问题,请及时指正,我们共同进步,谢谢!
标签:斐波,什么,问题,最优,动态,规划,那契 From: https://www.cnblogs.com/TiAmo-bai/p/16633206.html