【面试题-算法】----面试经典算法题｜四人过桥问题详细解析

面试经典算法题｜四人过桥问题详细解析

一、题目描述🌉

题目：四人过桥问题 A (1min)、B (2min)、C (5min)、D (10min)，只有一把手电筒，桥最多同时过 2 人，必须带手电。求全部过桥最短时间。（还要算上回头送手电筒时间。）
现有四人：A(1min)、B(2min)、C(5min)、D(10min)。
约束条件：

1. 桥上最多同时通行2人；
2. 仅有1把手电筒，过桥必须携带手电；还要算上回头送手电筒时间。
3. 两人同行，耗时等于速度更慢者的时间；
4. 需要求出所有人全部过桥的最短总时间。

很多面试者会掉入思维陷阱，直接使用直觉方案，我们一起来拆解。

二、容易想到的错误方案❌

❌直觉思路一：使用最慢的2个组合先过，
步骤：

1. C+D过桥 → 10min
2. C返回 → 5min
3. A+C过桥 → 5min
4. A返回 → 1min
5. A+B过桥 → 2min
   总耗时：2+1+5+1+10 =23min

❌直觉思路二：使用A来回运送手电，依次带所有人过桥。
步骤：

1. A+B过桥 → 2min
2. A返回 → 1min
3. A+C过桥 → 5min
4. A返回 → 1min
5. A+D过桥 → 10min
   总耗时：2+1+5+1+10 =19min

该方案并不是最优解，核心缺陷：C、D分开过桥，重复消耗大量慢速时间。

三、最优通行方案✅

核心关键字策略：让最慢的两个人结伴过桥，只支付一次慢速耗时。
✅完整执行步骤：

1. A、B一起过桥 ⏱️ 耗时2min
2. A携带手电返回 ⏱️ 耗时1min
3. C、D一起过桥 ⏱️ 耗时10min
4. B携带手电返回 ⏱️ 耗时2min
5. A、B一起过桥 ⏱️ 耗时2min

总耗时计算：2+1+10+2+2 =17min

四、算法核心思想💡

本题考察贪心策略的取舍思维。
误区：单纯认为「最快的人不停往返」就是最优。
正确关键字逻辑：
慢速人员（C、D）过桥成本极高，尽量安排两人同行，减少高额时间重复支出；
利用速度靠前的A、B配合完成手电传递，平衡返程开销。

两种备选策略对比总结：

1. 快者护送慢者：适合慢速差距不大场景
2. 最慢两人结伴：适合存在耗时差距极大人员，本题最优选择

五、面试延伸提问📝

面试官经常追加问题：

1. 能否使用动态规划通用求解N人过桥问题？
2. 怎么用代码枚举所有通行状态，自动算出最小耗时？

六、总结📌

四人过桥是大厂高频思维面试题，记住关键结论：
优先安排最慢两人共同过桥，规避多次支付高额耗时，本题最短时间为17分钟。
答题不要只报答案，一定要把策略对比讲清楚，体现算法思维。