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