内容目录
一、DP算法设计
因为要考虑最短等待时间和，所以对于每个人来说应尽可能地减少等待时间，但是同时要考虑到不能对他人的等待时间造成太大影响。最好的处理办法就是尽可能保存每个人所有可能的等待时间情况下的最优值。
设为第个人等待分钟的情况下前个人的最小等待时间和，为第个人等待时间分钟的情况下的最小等待时间和(即)，为第个人的到达时间。
第个人等待分钟出发会有两种可能的情况，即是否和上一个人同一班车走。
如果不和上一个人同一班车走的话，为确保第i个人在j分钟的时候车子已经回来了，那么第个人等待时间必小于，则。
考虑一个人的最大可能等待时间，车应该恰好在他到达之前出发，同时为了和下一个人一起走（可能这样总时间更短），他等待了不超过秒（因为超过秒车他完全可以不等下一个人，因为下一个人到达前，时间足够车子一个来回了），故有对于。
二、DP算法的三个基本属性
1.最优子结构
前个人的最小等待时间和为，且必有
2.无后效性
只与有关，在决定之前，不会和产生联系；同理。
3.子问题重叠
对于求法一样.
三、算法中使用的数据结构说明
为二维数组，为一维数组
四、算法评估
1.时间复杂度：
2.空间复杂度：
3.可优化处：
1）时间复杂度：
可以把同一时刻的人归为一批，更改为第批到达的人的时间，增设 c[i]记录第批到达的人数。对于第批与第批不同车的情况方程更改为
新的Dp方程为
2）空间复杂度：
在程序编写的过程中和可以只开一维数组，因为他们的第个状态只和有关，循环更新一维数组即可。
