动态规划是另一类常用的算法设计思想，广泛应用于组合优化问题。
核心思想
对问题自下而上地求解，将中间结果记录下来以供后面使用，用空间换取时间。
最简单的例子—— Fibonacci数列
Fibonacci数列的定义是：
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
递归是自上而下求解，写法如下：
//递归法
int FibRec(int n){
if (n<=1){
return n;
}
if (n==2){
return 1;
}
return FibRec(n-1) + FibRec(n-2);
}
用递归树的方法可知，其算法复杂度为O（2^n），效率极差。
观察到每一项都是前两项的和，子问题重叠较多，递归法重复计算很多。所以考虑把中间结果记下来，供后续重复使用，这样就效率大增了。
备忘录法C++代码实现如下：
//备忘录法
int Fib(int n){
if (n<=0){
return n;
}
//备忘录
int* memo = new int[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i=2; i<=n; i++){
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
算法复杂度为O(n)，空间复杂度也为O(n)。
过桥问题
题目：在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
这个视频能帮助理解如何得到最优方案。
吊桥谜题Can you solve the bridge riddle
该问题可用动态规划法求解，关键在于写出递推方程。
易知：
F(1) = T(1)，一人直接过去
F(2) = T(2)，俩人一起过去
F(3) = T(2) + T(1) + T(3)，1、2先过去，1回来接3过去
当n>=4时，按照上面视频中的方法：先让1、2过去，然后1回来；再让最慢和次慢的一起过去，然后2回来；最后1、2一起过去。
F(n) = F(n-2) + F(1) + T(n) + F(2) + F(2)
得到这个递推方程，剩下的就和Fibonacci数列的求解一样了。
背包问题
总结
设计步骤可以总结为：
- 划分子问题。
- 确定优化函数，判断是否满足优化原则，即：一个最优决策序列的任何子序列本身，一定是相对于子序列的初始和结束状态的最优决策序列。简单来说，就是最优序列的子序列也是最优的。
- 列出关于优化函数的递推方程（或不等式）和边界条件。
- 视情况设立标记函数，记录划分位置。
- 自底向上计算，以备忘录方法存储中间结果。
- 求得解后，根据备忘录（和标记函数）追溯出最优解。
