本文主要是介绍福州DAY7——DP（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OI三大难点就是图论、数论和今天所要讲的DP。这么简洁明了的说了，那么DP肯定是有所难度的。事实证明，我今天有点不能接受，导致今天讲的东西有一点不理解，不能完全消化。（虽然说，这是我第二次听DP了，可见我是个蒟蒻）
（1）动态规划基础
DP俗称动态规划，是运筹学的一个分支，是求解决策过程最优化的数学方法。既然提到了是数学方法，足以说明学DP要有一定的数学理念的。学习DP，我们先要了解DP的一些基础知识。
1.阶段：把所求的解问题的过程恰当的分成若干相互联系的阶段，以便于求解。一般阶段就是递推最外层的循环。
2.状态：表示每个阶段中面临的自然状况或客观条件，是不可控制的因素。
3.状态转移：从一个阶段的一个状态转移到下一个阶段的某个状态的一种选择行为，叫做状态转移。
既然了解了DP的一些基础知识，那么我们再来讲讲DP在什么时候用吧，也就是使用DP的动机。
（2）最优化原理和最优子结构
最优化策略具有这样的性质，不论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最有策略。简单地说，一个最优化的决策的自决策一定是最优的。一个问题满足最优化原理又称其具有最有子结构的性质。每一个子问题都最有的情况下，原问题会最优，这就是最优化原理。存在最优化原理的问题，就称其拥有最优子结构。动态规划过程就是由局部最优解推出最终最优解的过程。
（3）无后效性
无后效性，复杂的说：及在此后过程的演变中不再受到此前的各种状态以及决策的影响。简单地说：就是未来与过去无关”。通俗的讲，就是在考虑问题的过程中，如果知道了当前状态的最优值，我们可以无视当前的状态是怎么来的，都不会影响到之后的答案，这就是无后效性。实际上，无后效性和最优子结构的本质是一样的，即我们可以利用无后效性定义状态（找到存在无后效性的地方或者属性就是一个阶段），进一步利用最优子结构去定义状态的函数或状态转移方程。
（4）子问题的重叠性
其实我们不难发现，大部分动态规划的题目都可以用搜索来解决。的确，动态规划实际上就是搜索的优化，可以将原来具有阶乘级别的搜索变得更加有效。因为DP解决了搜索中重复的子问题，这就是DP的根本意义。为了避免重复计算，我们把每一种状态都记录了下来，以空间换时间。其实就是以递推的形式来展现记忆化搜索。
（5）DP一般的解题步骤
1.判断问题是否优最优子结构
2.把问题分成若干个阶段
3.写出状态转移方程
4.找出边界条件
5.将已知边界值带入方程
6.递推求解
说了这么多了，就来道题吧！
斐波那契数列：
题目描述：
这TM还需要题目描述？求斐波那契数列的第n项。解题分析：
这种题目一上来就打爆搜，AC算我输。我们不妨先用搜索的想法来求第n项，非常简单。
int fbnq(int k) {if(k==1)return 1;if(k==2)return 2; //边界条件 <——————此处应有代码return (fbnq(k-1)+fbnq(k-2)); }
但是这显然是不行的，时间复杂度将会是阶乘级别的。为什么呢？因为每一次求的时候，我们会有很多已经求出来的值再求一遍，这使效率大大降低。所以，我们可以用空间换时间，用一个数组专门记录每一个状态的值，每一次找到当前状态时不需要及需求下去，而是直接返回这个值，那么时间应该就是O（n）的。这就是记忆化搜索，代码就不给了。
int a[100000]={0}; //记录当前状态的数组int fbnq(int k)
{if(a[k]!=0)return a[k]; //如果当前状态有值，直接返回if(k==1)return a[k]=1;if(k==2)return a[k]=2;return a[k]=(fbnq(k-1)+fbnq(k-2));
}
当然，我们也可以找出递推式，我们可以发现a[k]=a[k-1]+a[k-2]。这就是状态转移方程，于是，我们就可以用for循环一遍解决了，效率也是O（n）
for(int i=3;i<=n;i++)
{a[i]=a[i-1]+a[i-2];
}这篇关于福州DAY7——DP（一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
