动态规划，就是把原问题分解成相对简单的子问题的方法。
我们先看一下例题：
斐波那契数列
根据以前学习的知识，我们可以快速写出一个函数：
long long F(int n) {
if (n == 1 || n == 2) return 1;
else return F(n – 1) + F(n – 2);
}
尽管这个函数可以准确得完成斐波那契数列问题，但是，它真的高效吗？
首先，和直接手动自定义，在的时候，往前枚举1和2，四的时候枚举2和3，而枚举到3时又要枚举1和2……
那么，有没有更好的办法呢？
有，当然有！他就是动态规划DP！
动态规划优化方法
DP常常适用于具有重叠子问题或者最优子结构性质的问题，它将问题转化为多个子问题，并且记录这些子问题的结果，逐步得到最终问题的结果。
记录，即存储计算过的答案。下次处理时，计算过的直接调用，无需重复计算。
如此一来，只需一个数组，就可以优化很多了。
long long F1(int n) {
if(ans[n]!=-1) return ans[n];
if(n==1||n==2) return ans[n]=1;
return ans[n]=F1(n-1)+F1(n-2);// 状态转移方程
}
注释中出现了一个新奇玩意儿动态转移方程，What is it？
当前状态的前一个状态 就是状态转移，说白了，就是“ans[n]如何得到？”这个问题用式子表达出来。得到了状态转移方程，你就成功了一大半了。
然后，就可以用递推（for循环）或者递归（函数）完成问题了。
再说一句：我个人更喜欢递推，递推速度稍微快一丢丢
完