阿里经典面试题——小朋友最短时间过桥问题——动态规划

缘起

阿里笔试曾经考过下面的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题目：在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入：

两行数据：

第一行为小朋友个数n

第二行有n个数，用空格隔开，分别是每个小朋友过桥的时间。

输出：

一行数据：所有小朋友过桥花费的最少时间.

样例：

输入

4
1 2 5 10

输出

17

分析

显然DP， 首先考虑一下送n个人如何减少问题的规模. 我们假设T[0,…,n-1]是升序（一个sort搞定的事情）.并记dp(n)为T[0,..,n-1]过桥的最短时间.

我们总得把T_{n-1}送过去吧? 送过去的方式只有以下2种.

第一种: T_{n-1}的过桥伙伴在T_{n-1}过桥之后立马回去了.

则这种情况下的最佳策略就是

T0送T_{n-1}过桥，然后T0回来还手电筒，则尚未过桥的人 有T[0,..,n-2], 于是这种情况下

最少时间是 T[n-1]+T[0]+dp(n-1)

第二种 T_{n-1}的过桥伙伴在T_{n-1}过桥之后没有立马回去

那么总得有人把手电筒送回去吧? 那就是第三者(它此时已经过桥了). 而这个第三者当时过来一定不是和T_{n-1}以及他的伙伴中的任何一个人一起过来的, 但是第三者不可能是一个人过的桥，不然没有人把手电筒还回去, 所以一定存在第四个人. 也就是整个过程涉及4个人。

则这种情况下的最佳策略就是

T0（第三者）、T1（第三者当时过河的伙伴）过河，T1留在那边，T0回来还手电筒，花费T0+T1时间，然后

T_{n-1}和T_{n-2}结伴过桥，回来的时候T_{n-1}和T_{n-2}都不回来，而是T1回来，花费时间 T_{n-1}+T1, 此时尚未过桥的人有 T0,.., T_{n_3}, 所以这种情况下，最短时间是

dp(n-2)+2*T1+T0+T[n-1].

注意，为什么是T0,T1,T_{n-2}来陪伴T_{n-1}玩这场游戏? 因为如果不是的话，则通过简单替换就可以证明计划不是最优的（算法导论中称之为copy-paste论证）

所以最后的递推公式是

1
2
假设 T[0,..,n-1]升序排序，则有
dp(n) = min{dp(n-1), dp(n-2)+2*T1} + T[0]+T[n-1]， n>=2, dp(0)=T[0], dp(1)=T1

滚动数组（这里采取的是无脑滚动）可以优化空间复杂度. 最后的C++实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
//#define LOCAL
using namespace std;

const int MAX_N = 55;

int T[MAX_N], n, dp[2];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	for (int i = 0; i<n; scanf("%d", T+(i++)));
	sort(T, T+n);
	dp[0] = T[0], dp[1] = T[1];
	for (int i = 2; i<n; i++) dp[i%2] = min(dp[(i-1)%2], dp[(i-2)%2]+(T[1]<<1))+T[0]+T[i];
	printf("%d\n", dp[(n-1)%2]);
	return 0;
}

时间复杂度是O(N), 空间复杂度是O(1), 即就地算法.

顺便说一句——此题为什么n的范围要到50? 这就是为了卡暴力搜索. n=50, 如果dp的话，答案毫秒级别可以出，如果暴搜的话，估计明年还不一定能出（除非适当剪枝~）

唯一的遗憾就是此题没有找到地方可以提交——不ac的算法都是耍流氓~

延伸一下——如果同时允许k个人同时过桥呢? 其实也是一样的思路.

按照与 T_{n-1}一起过河的伙伴是否立即回去还手电筒分成两种情况

  1. 如果是，则最优是T0是T_{n-1}的伙伴. 则最优为 dp(n-1)+T0+T_{n-1}
  2. 如果不是, 则最优是T0和T1(注意，不需要T2,…,T_{k-1}参与，否则他们一起回来的时候，需要耗时T_{k-1}>=T1)、T_{n-1,…,n-k} 一起参与这个游戏. 和一样的过程. 最优为 dp(n-k)+2*T1+T0+T_{n-1}

所以得到以下递推公式

1
2
假设 T[0,..,n-1]升序排序，则有
dp(n) = min{dp(n-1), dp(n-k)+2*T1} + T[0]+T[n-1]， n>=k, dp(0)=T[0], dp(1)=T1,...,dp(k-1)=T[k-1]