[LeetCode]Race Car

Brute force的做法就是BFS找最短路径，每一次尝试A和R看最后能不能到达目标坐标。但是这样时间复杂度太高了如果最少需要的操作为d，那么时间复杂度为O(2^d)，碰到大的数字直接就TLE了。我们可以注意到，在上面BFS的搜索当中，有很多没有必要的状态我们可以避免，比如连续的RRRR，所以我们需要想办法排除不必要的状态。当我们处于坐标x，并且x小于target时，我们只需要考虑所有向右的move。我们可以向左move，但是最终都是为了向右move，因为向左Reverse之后move再Reverse回来可以帮我们调整在x处步长的大小，我们可以根据这个调整到任意2^k大小的步长。也就是说在x处，x有带权边连向所有值为x + 2^k的元素，假设当前在x处的速度为v，那么：

• x到x + v的边长为1
• x到x + 2^k(除v之外)的边长为2 * (k + 1)  + 1 = 2 * k + 3，两次reverse，向左k步向右k步调整步长为2^k回到x，再加最后一步

k的上界是满足2^(k - 1) <= target - x <= 2^k，因为我们如果超过了target，再继续向右移动就没有意义了。那么对于x > target的情况，也是一样的。

可能有人会说，如果我们通过一系列左移右移操作到达小于x的某点y，然后在y处调整步长不经过x继续向左寻找target可能会有更短的路。那么假设y经过一系列操作到达target，那么x只要模仿这些操作就可以的到达target + x - y的坐标(x只要调整步数和在y处的步数相同即可，消耗的步骤和y处是一样的)，此时我们只需要复制之前从x到y的操作就可以回溯x - y个单位从而到达target，我们从而可以保证从x出发的最短路径不会大于y处的最短路径。

很明显，这是一个带权图了，我们用dijkstra找最短路径即可，假设target为n，那么我们有N个节点，每个节点最多有log N条边，我们用c++的priority queue实现，由于不支持decreasekey的操作，我们允许重复的节点进入优先队列，出列的时候再去重。如果图有E条边，时间复杂度为O(E log E)，所以这个解法时间复杂度为O(N * log N * log (N * log N))。代码如下：

	struct Node
	{
	int pos, speed, steps;
	Node(int a, int b,int c)
	{
	pos = a;
	speed = b;
	steps = c;
	}
	};
	class Solution {
	public:
	int racecar(int target) {
	auto comp = [](const Node& lhs, const Node& rhs)
	{
	return lhs.steps > rhs.steps;
	};
	unordered_set<string> visited;
	priority_queue<Node, vector<Node>, decltype(comp)> q(comp);
	q.emplace(0, 1, 0);
	while(q.size())
	{
	auto node = q.top();
	q.pop();
	int curr = node.pos, speed = node.speed, steps = node.steps;
	string key = to_string(curr) + "-" + to_string(speed);
	if(visited.find(key) != visited.end())continue;
	visited.insert(key);
	if(curr == target)return steps;
	if(curr < target)
	{
	int k = 1, shift = 0;
	while(k <= target - curr)
	{
	q.emplace(curr + k, 2 * k, k == speed? steps + 1: 2 * (shift + 1) + 1 + steps);
	k <<= 1;
	++shift;
	}
	q.emplace(curr + k, -1, k == speed? steps + 2: 2 * (shift + 1) + 2 + steps);
	}
	else
	{
	int k = -1, shift = 0;
	while(abs(k) <= curr - target)
	{
	q.emplace(curr + k, 2 * k, k == speed? steps + 1: 2 * (shift + 1) + 1 + steps);
	k <<= 1;
	++shift;
	}
	q.emplace(curr + k, 1, k == speed? steps + 2: 2 * (shift + 1) + 2 + steps);
	}
	}
	return -1;
	}
	};

view raw Race Car_dijkstra.cpp hosted with ❤ by GitHub

我们跑完test case可以看到用时在500ms以上，显然不是很理想。一个可能的优化是，如果当前在x点的速度为v，那么我们需要回溯调整步长为大于v吗？按道理应该是不要的，所以我们可以再加一个限制，如果要调整的步长如果大于v，我们就剪枝。这个我并不太会证明，只是直觉上的优化，结果AC了，并且用时降低到200+ms。代码如下：

	struct Node
	{
	int pos, speed, steps;
	Node(int a, int b,int c)
	{
	pos = a;
	speed = b;
	steps = c;
	}
	};
	class Solution {
	public:
	int racecar(int target) {
	auto comp = [](const Node& lhs, const Node& rhs)
	{
	return lhs.steps > rhs.steps;
	};
	unordered_set<string> visited;
	priority_queue<Node, vector<Node>, decltype(comp)> q(comp);
	q.emplace(0, 1, 0);
	while(q.size())
	{
	auto node = q.top();
	q.pop();
	int curr = node.pos, speed = node.speed, steps = node.steps;
	string key = to_string(curr) + "-" + to_string(speed);
	if(visited.find(key) != visited.end())continue;
	visited.insert(key);
	if(curr == target)return steps;
	if(curr < target)
	{
	int k = 1, shift = 0;
	while(k <= target - curr && k <= speed)
	{
	q.emplace(curr + k, 2 * k, k == speed? steps + 1: 2 * (shift + 1) + 1 + steps);
	k <<= 1;
	++shift;
	}
	q.emplace(curr + k, -1, k == speed? steps + 2: 2 * (shift + 1) + 2 + steps);
	}
	else
	{
	int k = -1, shift = 0;
	while(abs(k) <= curr - target && abs(k) <= abs(speed))
	{
	q.emplace(curr + k, 2 * k, k == speed? steps + 1: 2 * (shift + 1) + 1 + steps);
	k <<= 1;
	++shift;
	}
	q.emplace(curr + k, 1, k == speed? steps + 2: 2 * (shift + 1) + 2 + steps);
	}
	}
	return -1;
	}
	};

view raw Race Car_dijkstra_with_pruning.cpp hosted with ❤ by GitHub

如果我们进一步考虑的话，如果x距离target还很遥远并且当前速度为v，我们还需要考虑把步长调整到小于v的情况吗？按道理也应该是不用的(很可惜我还是不会证明)，假设k满足条件2^(k - 1) - 1 <= target <= 2^k - 1那么我们搜索target的策略可以简化到如下情况：

• 一直走到达2^k - 1，然后Reverse，向左继续搜索，这样的话，就变成了从0开始搜索2^k - 1 - target的情况
• 一直走到2^(k - 1) - 1然后Reverse向左走到某点z，然后从z继续向右搜索。当前的步长为2^(k - 1)，我们向左走的距离不会超过这个步长，否则只是无意义地增加步数，遍历所有小于这个值的步长。假设我们向左走了m(m < k - 1)步到达z，也就是2^m - 1的距离，那么问题也就变成了，从0开始搜索target - (2^(k - 1) - 1 - 2^m - 1) = target - 2^(k - 1) + 2^m的问题

如果我们用dp[i]表示，从0开始搜索i需要的最小步数。假设n满足条件2^(n - 1) - 1 <= target <= 2^n - 1，我们根据上面可以推得递推公式：

•  dp[i] = n + 1 + dp[2^n - 1 - i]，对应第一种情况，连续n个A，之后一个R
• dp[i] = n + m + 1 + dp[i - 2^(n - 1) + 2^m], where m < n - 1，第二种情况，n - 1个A，一个R，之后m个A，再一个R

根据递推公式实现即可，时间复杂度O(n * log n)，memorization的写法：

	class Solution {
	public:
	Solution()
	{
	memset(dp, 0, sizeof(dp));
	}
	int racecar(int target) {
	if(dp[target] > 0)return dp[target];
	int n = static_cast<int>(log2(target)) + 1;
	//dp[i] represent minimum steps required from 0 to i with starting speed 1
	//we have two ways to approach i:
	// 1. 0->2^n - 1 and turn back, first n + 1 steps(n*A + R), then dp[2^n - 1 - i], dp[i] = n + 1 + dp[2^n - 1 - i]
	// 2. 0->2^(n - 1) - 1, turn back, move m steps back and turn back again, when arriving
	// 2^(n - 1) - 1, we can get a smaller step. First n steps, then m + 1, then dp[i - (2^(n - 1) - 1 - 2^m + 1)]
	// dp[i] = n + m + 1 + dp[i - 2^(n - 1) + 2^m], where m < n - 1
	//base case: if i == 2^n - 1, dp[i] = n
	if(1 << n == target + 1){dp[target] = n;return n;}
	dp[target] = racecar((1 << n) - target - 1) + n + 1;
	for(int m = 0; m < n - 1; ++m)
	dp[target] = min(dp[target], racecar(target - (1 << (n - 1)) + (1 << m)) + n + m + 1);
	return dp[target];
	}
	private:
	int dp[10005];
	};

view raw Race Car_dfs.cpp hosted with ❤ by GitHub

bottom-up的写法：

	class Solution {
	public:
	int racecar(int target) {
	vector<int> dp(target + 1, 0);
	for (int i = 1; i <= target; ++i)
	{
	int n = log2(i) + 1;
	if ((1 << n) == i + 1) { dp[i] = n; continue; }
	dp[i] = n + 1 + dp[(1 << n) - 1 - i];
	for (int m = 0; m < n - 1; ++m)
	dp[i] = min(dp[i], dp[i - (1 << (n - 1)) + (1 << m)] + m + n + 1);
	}
	return dp[target];
	}
	};

view raw Race Car_dp.cpp hosted with ❤ by GitHub