动态规划

问题：最短路径路径问题，从起点到终点的最短路径

解决方法是利用动态规划，状态转移方程

为什么要从后往前进行判断呢？
因为单纯判断最短距离时，从后到前或者从前到后都是可以的。但是在实际编程时，对于这个图，我们用的是
struct node {
struct *node d;【向下顶点】
struct *node u;【向上顶点】
int d,u;【距离】
}
所以如果我们从前往后，有状态转移方程
F(A)=min{d1(A->D),d2(A->D)}
但是因为判断的是A的，但是d,u是存储在D中，所以不好编码。
而且从前往后对于D是无判断的，所以你无法知道具体路径。
而从后往前可以解决：

优化原则 ：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列

矩阵链

两个矩阵的乘法

即P(i,j)*p(J,K) 总共的乘法次数为IJK

现在来看矩阵链

所以对于矩阵链{P1,P2,P3,P4----PN} ，实际即求

递归表示方法：

’
伪代码表示为：

计算时间复杂度表示：


所以可以看到时间复杂度并没有相比于遍历减少多少，仍然是指数级，这是因为存在多个重复运算，如下图所示：

遍历表示方法

从底到顶开始，即先从长度为1的矩阵开始，再计算长度为2的，一依次类推。
每个长度矩阵只计算依次

伪代码如下

其中5——6是计算一种情况，
即对于P(A1,A2,A3,A4) i=1，步长为3时，计算A1(A2A3)
其实是可以放入for循环的【注意初值m(i,j)】



时间复杂度：

投资问题

完全背包问题

递推公式：
解析
Fk-1(y)：表示不购买这种物品
Fk(y-wl)+vk：表示再次购买一个(wk,vk)。注意这里只是购买一个【也许已经是第i个此种物品】，因为Fk(y-wk)也会往回进行判断Fk(y-wk)=max{Fk-1(y-wk),Fk(y-2*wk)+vk}
当y<wk时候，即不足以购买此种物品，只能不购买所以Fk(y-wk)=Fk-1(y-wk)

注意此矩阵是for(k=1 to 4){
　　　　　　　for(y=1 to 10)
　　　　　　}

伪代码：

时间复杂度：

最长公共子序列

蛮力算法：

动态规划：
首先明确前后依赖关系

得到递推方程

伪代码：