动态规划（算法+理论） ★最短路径

首先介绍动态规划的概念：
①问题是由交叠的自问题构成的，是对给定问题求解的递推关系中的相同类型的*更小子问题的解*dp+回溯
②从顶至下，避免计算不需要计算的小解（记忆）
③求解最优化问题可以用动态规划
动态规划下笔写代码前先去顶递推式
直接看实例：
一、币值最大化问题
给定一排n个硬币，其面值均为正整数c1，c2，c3……cn，这些整数并不一定两两不同，请问如何选择硬币，使得在其原始位置互不相邻的条件下，所选金额最大。

上述最大金额可用fn来表示，为了得到fn的递推关系，将所有可行的选择分为两组，包括最后一枚硬币和不包括最后一枚硬币的。

F(N)={① 包括最后一枚硬币 cn+f（n-2）
②不包括最后一枚硬币 f（n-1）
其递推式：
**则 fn=max{cn+f(n-2),f(n-1)}
f(0)=0,f(1)=c1**

coinrow(c[1..n])
//应用上述递推式，自底向上求最大金额
//在满足所选硬币不相邻的条件下，从一排硬币中选择最大金额的硬币
//输入：数组c保存n个硬币的面值，下标从1开始
//输出：可选硬币的最大金额
f[0]=0;
f[1]=c[1];
for(i=2;i<=n;++i)
   f[i]=max{c[i]+f[i-2],f[i-1]};
return f[n];

可用上述算法来求解一排硬币5 1 2 10 6 2，其最大金额为17

求出最大值后利用回溯计算过程来确定构成最大金额的硬币元素。
在最后一次引用递推方程时，是c6+f(4)给出了最大金额17.这意味着c6是最优解的一部分，继续回溯f(4)的计算，最大金额由c4+f(2)给出，这意味着c4也是最优解的一部分，最后计算f(2)的时候，其最大值由F(1)产生，这意味着c2不是最优解的一部分，而c1是。故得出结论 c1 ，c4，c6
该过程显然耗费了o(n)的时间和空间。远远优于利用递推方程自顶向下递推求解或者穷举查找。

二、找零问题
需找零金额为n，最少要用多少面值为d1

changemaking(D[1...m],n)
//应用dp求解，找出使硬币加起来等于n时所需最少的硬币数目
//其中币值为d1<d2<d3<.......<dm，d1=1
//输入：正整数n以及用于表示币值的递增整数数组D[1..m],D[1]=1
//输出：总金额等于n的硬币最少的数目
f[0]=0;
for(i=1;i<=n;++i)
   temp=max;
   j=1;
   while( j<=m&&i>=D[i])
      temp=min(f[i-D[j]],temp);
      j=j+1;
   f[i]=temp+1;
return f(n);

则对于n=6，币值为1，3，4的硬币应用上述算法产生的结果是2，回溯之后硬币集合为2个3

**总结：
1找出递推关系
2从底向上
3令f(0)=0
4每步选最优步**

应用：背包问题
记忆法：将自顶向下和自底向上的方法结合起来
★对必要的自问题只求解一次
思路：
对于i个物品，承重量为j的背包的最优子集，自顶向下则考虑第i个物品能否放进去

{ 不行则考虑 F(i-1,j)
行则考虑 max{F(i-1,j),F(i-1,j-weight[i])+value[i]}
不放第i个物品和放第i个物品
初始条件： f(i,0)=0,f(0,j)=0
对上述递推式的解释：可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别，包括第i个物品的子集和不包括第i个物品的子集，则有：
（1）根据定义，在不包括第i个物品的子集中，最优子集的价值为F(i-1,j)
（2）在包括第i个物品的子集中，（j-wi>=0）最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成，此时最优子集的价值为max{F(i-1,j),F(i-1,j-weight[i])+value[i]}

应用：最优二叉查找树