[MeetCoder]Cross Bridge

N people wish to cross a bridge at night. It’s so dark around there that they have to cross the bridge under the help of a little lamp. Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such that a maximum of 2 people may cross at a time.

Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one. How fast can you get all N people over the bridge?

经典的过桥的问题，第一眼很容易觉得这会是贪心解法的题目。因为每次都要有人过桥回来送手电筒，那么我们每次让跑的最快的送就可以。但是考虑例子v = [1,2,5,10]，如果我们每次让v[0]跑来会送手电筒，那么总时间为2 + 1 + 5 + 1 + 10 = 19，但实际上最快的时间是17（当然这道题贪心也可以做就是没那么直观，感兴趣的可以google）：

• v[0]和v[1]过桥，用时2
• v[0]带手电筒回，用时1
• v[2]和v[3]过桥，用时10
• v[1]回，用时2
• v[0]和v[1]过桥，用时2

我们可以看出贪心之所以不行是因为每次跑的最快的人都要来回过桥，从而我们浪费了让两个相对慢的人一起过桥缩短总时间的机会。

如果我们从子问题开始考虑用DP来解决这个问题，我们把所有人按照用时从少到多sort，得到数组v。我们考虑前i个人所用的总时间DP[i]，我们有递推公式：

• DP[i] = DP[i - 1] + v[0] + v[i]，前i - 1个人已经过桥，最快的人回来送电筒然后和第i个人一起过桥
• DP[i] = DP[i - 2] + v[0] + v[i] + 2 * v[1]，前i - 2个人过桥，最快的人送电筒回来，第i - 1和第i个人过桥，第二快的人送电筒回来然后和最快的一起过桥

我们根据这个递推公式计算即可。时间复杂度空间复杂度均为O(n)，用滚动数组可以优化到常数空间，普通DP代码如下：

	//http://www.meetcoder.com/problem.php?id=45
	//N people wish to cross a bridge at night. It’s so dark around there that they have to cross the bridge under the help of a little lamp.
	//Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such
	//that a maximum of 2 people may cross at a time.
	//Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one.
	//How fast can you get all N people over the bridge?
	class Solution {
	public:
	int bridge(vector<int> &v) {
	int len = v.size();
	//sort v from smallest to largest
	//dp[i] represents minimum time required for first i + 1 people to cross the bridge
	//dp[i] = min(dp[i - 1] + v[0] + v[i], dp[i - 2] + v[0] + v[i] + 2 * v[1])
	sort(v.begin(), v.end());
	vector<int> dp(len);
	dp[0] = v[0];
	dp[1] = v[1];
	for(int i = 2; i < len; ++i)
	dp[i] = min(dp[i - 1] + v[0] + v[i], dp[i - 2] + v[0] + v[i] + 2 * v[1]);
	return dp[len - 1];
	}
	};

view raw Crossing Bridge.cpp hosted with ❤ by GitHub

优化后的代码：

	class Solution {
	public:
	int bridge(vector<int> &v) {
	int len = v.size();
	//sort v from smallest to largest
	//dp[i] represents minimum time required for first i + 1 people to cross the bridge
	//dp[i] = min(dp[i - 1] + v[0] + v[i], dp[i - 2] + v[0] + v[i] + 2 * v[1])
	sort(v.begin(), v.end());
	if(len == 1)return v[0];
	vector<int> dp(2, 0);
	int e = 0;
	dp[0] = v[0];
	dp[1] = v[1];
	for(int i = 2; i < len; ++i, e ^= 1)
	dp[e] = min(dp[e ^ 1] + v[0] + v[i], dp[e] + v[0] + v[i] + 2 * v[1]);
	return dp[e ^ 1];
	}
	};

view raw Crossing Bridge_rolling_array.cpp hosted with ❤ by GitHub