动态规划怎么求解双击流水车间问题

双击流水车间问题是一个经典的动态规划问题，可以使用以下步骤求解：

1. 定义状态：设f(i,j)表示第i台车间在第j个时间段结束生产的最小时间。

2. 状态转移方程：对于第i台车间，其在第j个时间段结束生产的最小时间可以由两种情况得到：一是前面的车间在第j个时间段结束生产，这时第i台车间要等待前面车间的加工完成，因此第i台车间的生产时间为f(i-1,j)+p(i,j)，其中p(i,j)表示第i台车间在第j个时间段加工的时间；二是第i台车间在前面的时间段就已经完成了生产，这时第i台车间的生产时间为f(i,j-1)+p(i,j)。

综上所述，状态转移方程为：f(i,j) = min{f(i-1,j)+p(i,j), f(i,j-1)+p(i,j)}

3. 边界条件：第1台车间在任何时间段都需要等待前面的车间生产完成，因此f(1,j) = f(1,j-1)+p(1,j)。第一个时间段内所有车间都需要完成生产，因此f(i,1) = f(i-1,1)+p(i,1)。

4. 求解最优解：根据定义，最小化最后一台车间在整个生产过程中的结束时间即可得到最优解，即min{f(n,j)}，其中n为车间的数量。

5. 优化空间复杂度：由于每个状态只与前一行和当前行的状态有关，因此可以使用滚动数组来优化空间复杂度，将状态数组f(i,j)缩减为f(j)。