?

动态规划

动态规划是运筹学的一个方向，就是把多级最优化问题分解成一系列的单阶问题。在不断增加的过程中，不断的计算当前问题的最优解。

一般分为如下四个部分：

汽车生产线问题

这个问题是《算法导论》的动态规划的例题，我自己觉得这道题比较简单而且典型，所以就解释下这个题目：

Colonel汽车公司在有两条装配线的工厂里生成汽车。每一条装配线上有n个装配站，
两条生产线上相同位置的装配站功能相同，但所需时间不同，并且汽车底盘在两条
装配线间转移要花费一定的时间。如下图所示两条生产线。
vc+88rWltcTKx6OsztLDx9a709DBvdbWx+m/9qOs0rvW1srH1NrXsMXkz98xyc/KsbzktsyjrNK71tbKx9Ta17DF5M/fMsnPyrG85LbMoaM8L3A+DQo8cD682cjnsanBpsvRy/ejrMyw0MTIpcvjtcO7sKOo0rK+zcrHtd256bXEsOy3qKOpoaPKsbzkuLTU077NyscyXm6jrNXiuPbKx7K7v8m908rctcShozwvcD4NCjxwPtXiuPbKsbryztLDx7XEsOy3qMrHz8i007Xa0ru49s7KzOK/qsq8o6zXsMXkz98xLCAyyc/Wu9PQ0ru49nN0YXRpb26ho8THw7SxyL3PvPK1paOs0ruxyL3Pvs26w8HLoaO1sdPQwb249nN0YXRpb261xMqxuvKjrL7Nyse008nP0ru0zrHIvc+1xL3hufvW0CjSu7j2bGluZSAx1+62zKOs0ru49mxpbmUgMtfutswp1tC8zND4vNPJz7Wxx7BzdGF0aW9utcTWtbzM0PixyL3PoaM8L3A+DQo8cD7L+dLUztLDx7eiz9bKx8O/uPa1scewtcTX7tPFveKjrLa8sPy6rMHLyc/Su7TOtcTX7tPFveKhozwvcD4NCjxoMSBpZD0="代码">代码

代码就是我们从最开始，一直保存当前问题的最优解，然后去求的下一次的最优解。

//
//  main.cpp
//  DP_line
//
//  Created by Alps on 15/4/26.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 
    
      using namespace std; #define NUM 5 int main(){ int first[NUM];//到装备站1,i的最短路径长度 int second[NUM];//到装配站2,i的最短路径长度 int linef[NUM]; //从1进入的路径 int lines[NUM]; //从2进入的路径 int a[NUM]; //在装配站1,i 所需要呆的时间 int b[NUM]; //再装配站2,i 所需要呆的时间 int m[NUM]; //从装配站1,i-1 到装配站2,i的时间 int n[NUM]; //从装配站2,i-1 到装配站1,i的时间 int line[NUM]; //当前最短路经所经过的装配站 int f[NUM]; //当前最短路径长度 int 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
     
    

这个代码比较简单，精华就是那个for循环了。

测试用例如下：

3 2 3 4 4 3 3 6 6 3 2 3 5 2 2 3 2 4 3 4 4 3

假如有任何建议，欢迎评论。互相学习。谢谢。