参考：动态规划—装配线调度

一、动态规划

动态规划（dynamic programming）和分治算法类似，都是通过组合子问题的解来求解原问题，但二者并不等价。
分治算法和动态规划的区别：

1.分治算法：将原问题分解为互不相交的子问题，即子问题之间相互独立，再组合求解
2.动态规划：应用于子问题重叠的情况，即不同的子问题有相同的子子问题。
（子问题的求解是递归进行的，将其划分为更小的子子问题）

在这种情况下，分治算法会做许多不必要的工作，它会反复求解那些公共子问题；而动态规划对每个子问题只求解一次，将其保存起来，从而无需每次求解一个子问题都重新计算。

动态规划常用来求解最优化问题。在这类问题中，我们可以找到很多解，而我们需要找到一个最优解（最优解不唯一）。

设计一个动态规划的4步骤：（其实3步骤足以）

1.刻画一个最优解的结构特征
2.递归定义最优解的值
3.自底向上地计算最优解的值
4.用计算出的信息构造一个最优解

二、流水线调度

我们这里仅考虑两条线的问题
问题描述：一个公司在有2条装配线的工厂内生产，每条装配线有n个装配站，不同装配线上对应的装配站执行的功能相同，但是每个站执行的时间是不同的。在装配时，可以将部分完成的产品在任何装配站上从一条装配线移到另一条装配线上。请问如何操作可以使得装配时间最少？

如图所示，我们有两条装配线，刚上装配线时花费上线时间e；上线后，每一步都根据线路不同，有步骤S和当前步骤花费时间a；当我们需要转移时，花费时间t；下线时，花费下线时间x。

根据要求，我们可以得到如下图红线所示的最优方案（时间最少）

利用动态规划求解此问题

第一步 描述最优解的结构特征

我们看其最优解（最少时间），其结构组成应该就是其前一步的最优情况解。
也就是说，这一步是最少时间的话，前一步也应该是最少时间。
而前一步，会分为两种情况：
1.就从这一条线过来
2.从另外一条线转移过来

为了解决这个问题，即寻找通过一条装配线上的装配站j的最快线路，需要解决其子问题，即寻找通过两条装配线上的装配站的j-1的最快线路。

第二步 递归定义最优解

第三步 求出最优解

我们根据递归式可以看到，要求解最后的最优解，需要上一个步骤的最短时间，一直往底部走的话，我们会到达第一步。此时我们从第一步开始一步步地比较，取最小的值作为这一步的最优解，一直往上就可以解得最后的最优解了。

伪代码

求最小时间

打印路径

小结