动态规划：
和贪婪算法一样，动态规划对一个问题的解是一系列的决策过程，贪婪算法依据贪婪准则，做出的每一个抉择都是不可撤回的，在动态规划中，需要考察一系列抉择，已确定一个最优抉择序列是否包含一个最优抉择子序列。
例如，在上图中，要从节点1到达节点5，选择一条最短的路径，第一步可以选择的顶点为2，3，4。假设选择顶点3， 然后决定如何从顶点3到达顶点5。如果选择了一条从顶点3到顶点5一条不是最短的路径，那么即使第一步选择了从顶点1到顶点3这条最短的路径，连起来构成从1到5的路径也不是最短的。
所以在最短路径中，如果第一次选择的是某一个顶点v，那么接下来所选择的从v到d的路径必须是最短的。
2. 背包问题：
在0/1背包问题中，需要选择 的值，如果选择，那么背包问题就转换为物品为背包容量认为c的问题，如果选择,则背包问题转换为物品为背包容量认为的问题.,另表示剩余背包的容量。
在第一次选择之后，需要考虑使用剩余的物品满足装在容量为 r 的背包，剩余的物品（2到n）和剩余的容量r规定了在第一次选择之后问题的状态。不管第一次选择的结果如何，必须是这个问题状态的一个最优解。如果不是，那么必有一个更好的选择，假设为,于是便是初始问题的一个更好的解。
当最优抉择包含最优抉择系序列的时候，可以建立动态规划递归方程，可以高效的解决问题。
0/1背包问题：
在背包问题中，最优选择序列由最优选择子序列构成，假设f(i,y) 表示剩余容量为y, 剩余物品为 i，i+1，...n的背包问题的最优解的值（0/1）。
剩余第n个物品，如果剩余的容量y大于该物品的体积 ，则 f(n,y) 的返回值为p_n,否则为0；
所以有：
根据最优序列由最优子序列构成的结论，可以得到上面的递推公式。
所以无论第一次的选择是什么，接下来的选择一定是当前状态下的最优选择。称此为最优原则。
动态规划求解的步骤：
1.证实最有原则是适用的
2. 建立动态规划的递归方程
3. 求解动态规划的递归方程以获得最优解
4. 沿着最优解的生成过程进行回溯
关于编程求解动态规划的问题：
在求解动态规划递归方程的规程中，应该避免递归中的重复计算。可以通过以迭代的方式来避免递归过程中的重复计算。迭代方式和递归方式拥有相同的复杂度，但是迭代方式不需要附加的递归栈空间。
上述背包问题的递归写法：
#include <iostream>#include <algorithm>using namespace std;// 背包问题的递归解法int f(int i, int capacity){// 参数 ：// i:第i个物品// capacity: 背包剩余的容量int number_of_object = 3; // 物品的个数 int weight[] = {100, 14, 10}; // 每个物品的权重 int profit[] = {20, 18, 15};if(i == number_of_object){return (capacity < weight[number_of_object-1]?0:profit[number_of_object-1]); // 递归的终止条件 } if(capacity < weight[i-1]){return f(i+1, capacity);}return max(f(i+1, capacity), f(i+1, capacity-weight[i-1])+profit[i-1]);}int main(int argc, char *argv[]){cout << f(1, 116) << endl;return 0;}
上面的程序以递归的方式求解，递归需要额外的栈空间，下面对上述的递归方法做一下改进：
1. 在问题中，假设n=5, 物品的重量为weight = [2, 2, 6, 5, 4], 物品的权重profit = [6, 3, 5, 4, 6], 且c = 10;
求解 f(1, 10)的递归调用过程如下所示：
为了避免对 f(i,y) 的重复计算，可以建立一个列表对其值进行存储，在本题中，可以使用整形数组对数据进行存储，farray[i, y]
通过这种方法，可以将时间复杂度从原来的O(n^2)降到O(cn)
代码如下所示：
#include <iostream>#include <algorithm>using namespace std;// 背包问题的递归解法int f(int i, int capacity){// 参数 ：// i:第i个物品// capacity: 背包剩余的容量int number_of_object = 3; // 物品的个数 int weight[] = {100, 14, 10}; // 每个物品的权重 int profit[] = {20, 18, 15};if(i == number_of_object){return (capacity < weight[number_of_object-1]?0:profit[number_of_object-1]); // 递归的终止条件 } if(capacity < weight[i-1]){return f(i+1, capacity);}return max(f(i+1, capacity), f(i+1, capacity-weight[i-1])+profit[i-1]);} int f_1(int i, int capacity){// 参数// i: 剩余i, i+1,...n个物品// capacity: 剩余的背包容量// 利用矩阵farray[i][y]存储f(i,y)的值， 维度为(n+1)*(c+1) // n: 物品个数// c：背包的容量 int number_of_object = 5;int weight[] = {2, 2, 6, 5, 4};int profit[] = {6, 3, 5, 4, 6};int n = 5; int c = 10; int** farray = new int*[n+1];for(int k=0; k<=n; k++){farray[k] = new int[c+1];} for(int p=0; p<=n; p++){for(int q=0; q<=c; q++){farray[p][q] = -1;}}// 检查需要的值是否已经计算过了，如果已经计算过了，则直接返回 if(farray[i][capacity] > 0){return farray[i][capacity];}// 还没有计算过 if(i==number_of_object){farray[i][capacity] = (capacity < weight[i-1]?0:profit[i-1]);return farray[i][capacity];}if(capacity<weight[i]){farray[i][capacity] = f(i+1, capacity);} else{farray[i][capacity] = max(f(i+1, capacity), f(i+1, capacity-weight[i-1])+profit[i-1]);}int result = farray[i][capacity];// 释放内存for(int k=0; k<=n; k++){delete [] farray[k];} delete [] farray;return result; // 返回计算的值}int main(int argc, char *argv[]){cout << f_1(1, 10) << endl;return 0;}
矩阵乘法链
问题描述：
矩阵A(mxn)与矩阵B(nxp)相乘需用时，将mnp作为两个矩阵相乘所需时间的测量值，假设要计算多个矩阵的乘积，一种是(AB)C，另一种是A(BC)，虽然计算结果相同，但是时间性能会有很大的差异。
假设：
A(100x1), B(1x100), C(100x1)
1. (A*B)*C
所需时间 t=100*1*100 + 100*100*100 = 1010000, 此外，计算A*B需要100x100的矩阵来存储中间结果；
2.A*(B*C)
所需时间 t=1x100x1 + 100x1x1, 且只需要一个存储单元来存储中间结果：
将问题推广到一般的情况下，假设有q个矩阵相乘，M1xM2XM3....xMq, 则相乘的方式随着q的增加以指数及增长，因此，当q很大的时候，考虑每一种乘法顺序并选择最优者是不切实际的。
动态规划方法：
可以使用动态规划来求解一个矩阵相乘的乘法顺序，动态规划可以将算法的时间复杂度降为O(q^3)
