这几天一直再看，觉得看懂了一些，先记下来。
动态规划
动态规划是运筹学的一个方向，就是把多级最优化问题分解成一系列的单阶问题。在不断增加的过程中，不断的计算当前问题的最优解。
一般分为如下四个部分：
汽车生产线问题
这个问题是《算法导论》的动态规划的例题，我自己觉得这道题比较简单而且典型，所以就解释下这个题目：
Colonel汽车公司在有两条装配线的工厂里生成汽车。每一条装配线上有n个装配站， 两条生产线上相同位置的装配站功能相同，但所需时间不同，，并且汽车底盘在两条 装配线间转移要花费一定的时间。如下图所示两条生产线。
首先我们知道每个阶段的最短时间，都包含了上一阶段的最短时间。
而比较简单的是，我们只有两种情况，一种是在装配线1上时间短，一种是在装配线2上时间短。
假如暴力搜索，贪心去算得话（也就是递归的办法）。时间复杂就是2^n，这个是不可接受的。
这个时候我们的办法是先从第一个问题开始，装配线1, 2上只有一个station。那么比较简单，一比较就好了。当有两个station的时候，就是从上一次比较的结果中(一个line 1最短，一个line 2最短)中继续加上当前station的值继续比较。
所以我们发现是每个当前的最优解，都包含了上一次的最优解。
代码
代码就是我们从最开始，一直保存当前问题的最优解，然后去求的下一次的最优解。
;#define NUM 5int main(){linef[NUM]; a[NUM]; m[NUM]; line[NUM]; ea,eb,xa,xb; // ea为进入装配站1时间，eb为进入2的时间，xa为出装配站1的时间，xb为出装配站2的scanf(“%d %d %d %d”,&ea,&eb,&xa,&xb);for(int i=0;i<NUM;++i){scanf(“%d %d”, &a[i], &b[i]);}first[0] = ea + a[0];second[0] = eb + b[0];for(int i=0;i<NUM-1;++i){scanf(“%d %d”, &m[i], &n[i]);}for(int i=1;i<NUM;++i){if(first[i-1] + a[i] < second[i-1] + m[i-1] + a[i]){first[i] = first[i-1] + a[i];linef[i] = 1;}else{first[i] = second[i-1] + m[i-1] + a[i];linef[i] = 2;}if(second[i-1] + b[i] < first[i-1] + n[i-1] + b[i]){second[i] = second[i-1] + b[i];lines[i] = 2;}else{second[i] = first[i-1] + n[i-1] + b[i-1];lines[i] = 1;}}for(int i=0;i<NUM;++i){if(first[i] + xa < second[i] + xb){f[i] = first[i] + xa;line[i] = 1;}else{f[i] = second[i] + xb;line[i] = 2;}}for(int i=0;i<NUM;++i){printf(“station %d\n”,line[i]);}printf(“Distince is %d\n”,f[NUM-1]);return 0;}
这个代码比较简单，精华就是那个for循环了。
测试用例如下：
3 2 3 44 33 66 32 35 22 32 43 44 3
假如有任何建议，欢迎评论。互相学习。谢谢。
当你能爱的时候就不要放弃爱
