[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))。代码如下：

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

如果我们进一步考虑的话，如果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的写法：

bottom-up的写法：