题目大意：
赛车
你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）
你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶 。
当车得到指令 “A” 时, 将会做出以下操作： position += speed, speed *= 2。
当车得到指令 “R” 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1 ；否则将车速调整为 speed = 1。 (当前所处位置不变。)
例如，当得到一系列指令 “AAR” 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。
现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。
示例 1:
输入: target = 3
输出: 2
解释: 最短指令列表为 "AA" 位置变化为 0->1->3
示例 2:
输入: target = 6
输出: 5
解释: 最短指令列表为 "AAARA" 位置变化为 0->1->3->7->7->6
说明:
1 <= target（目标位置） <= 10000。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=818
解题思路分析：
这是一道Hard题目，最优解使用的是DP动态规划，但笔者实在是才疏学浅，看了几篇文章均没能摸到其公式精髓。隧改用BFS，这样思路一下子变得清晰易懂。执行效率虽不及最优解，但也可以勉强混到击败50%以上的成绩（这里需要感谢未达到50%解法的大力支持）。
言归正传，一般使用bfs时，多数情况下会在一个数组或是树形结构里进行搜索，边界条件也就是数组的边界或是树的叶子节点。然而这道题，赛车的可移动范围并不局限于起点到目标终点的范围内，如果不加限制，bfs很容易无限循环至天荒地老。。。
因此，首先考虑清楚边界条件是本解法的关键，想清这点之后，剩下的bfs部分都是常规操作。那么边界到底在哪里？我们先看起点这个位置，如果一上来我们就向着反方向开，势必会离我们的终点越来越远，再加上反向操作的步数，显然我们已经输在了起跑线上。因此可以明确，起点0是我们的左边界。接下来考虑右边界，题目的例子已经给出我们很好的例证，即使超出终点再掉头回来也是有可能存在最优解的，那么最多超出多少是我们可以承受的范围呢？这个数字不好计算，我们只能用一个可以简单被证明是正确的数字作为边界，即终点target乘以2。也就是说我们的bfs搜索范围是在 0 到 target * 2的范围内。简单来说明一下，这个target*2是如何定义的，首先声明这并不一定是最优的边界范围，但是是一个我们可以承受的搜索范围。因为target*2到target的距离刚好等于起点到target的距离，既然从起点处不能向后开，同理在target*2处继续向前开同样会增加操作的步数。写本篇文章前，我在利用反复提交代码测试了一下这个边界值，在target*1.3左右的范围内是可以通过所有TC，因此实际上1.3应该是比较接近最优边界值的数。不过不论边界是target的2倍或是1.3倍，都不会影响到最终的结果，我们使用2倍只不过多搜索了一些非最优解而已。执行速度上也是相差无几。
有了边界值，剩下就是如何做bfs，我们知道在边界范围内，每一步我们都有两种操作的可能，或者加速向前，或者转向，将这两种可能放入bfs中继续演化出更多的可能，直到找到目标终点为止，bfs操作的次数即是结果。
另外，bfs必须同时配搭memo记忆数组，防止大量的重复计算出现。也就是说不要在同一路径上反复折返。这里memo的key不能仅仅记录当前位置，还要记录当前速度，因为即使在相同位置，速度不同也会产生不同的结果。
我们看下详细的代码：
public int racecar(int target) {
// memo用来记录已经走过的点，防止重复走回头路
// memo中的值我们用position_speed形式的字符串记录
Set<String> memo = new HashSet<>();
// 因为在起点是边界值，不能向回走，将其存入memo
memo.add("0_-1");
// 同时第一步只能走出向前加速，因此将0_1存入memo
memo.add("0_1");
// 定义bfs用的Queue。泛型Pair中存的是当前坐标和速度
Queue<Pair> q = new LinkedList<Pair>();
// 将起点和起始速度加入Queue中，作为bfs的开始。
q.offer(new Pair(0, 1));
// 用于记录bfs的步数
int count = 0;
// bfs开始
while (q.size() > 0) {
// 记录当前bfs开始前Queue的size大小
int size = q.size();
while (size > 0) {
// 每搜索完一个节点，size减一。
// size变为0时，说明当前层的bfs搜索全部结束，此时count可以加一
size--;
// 从Queue中取出一个节点
Pair pair = q.poll();
// 该节点位置
int position = pair.position;
// 该节点速度
int speed = pair.speed;
// 当前节点加速的情况下，位置变为position + speed
int aPosition = position + speed;
// 如果加速后正好达到终点，返回count+1。
// +1是本次加速的操作
if (aPosition == target) {
return count + 1;
}
// 加速后速度变为原来的2倍
int aSpeed = speed * 2;
// 如果加速后的位置在边界之内，我们将此处位置和速度存入Queue中
if (aPosition > 0 && aPosition < target * 2) {
q.offer(new Pair(aPosition, aSpeed));
}
// 反向的情况下，速度变为1或者-1
int rSpeed = speed > 0 ? -1 : 1;
// 我们利用当前位置和速度作为key，存入memo数组，避免之后重复走
String key = position + "_" + rSpeed;
// 如果memo中不存在该key，说明曾经没有以相同的速度开到过这里
if (!memo.contains(key)) {
// 将key存入memo
memo.add(key);
// 同时将此处位置和速度存入Queue中
q.offer(new Pair(position, rSpeed));
}
}
// size变为0时，说明当前层的bfs搜索全部结束，此时count可以加一
count++;
}
// 返回结果
return count;
}
class Pair {
int position;
int speed;
Pair(int p, int s) {
position = p;
speed = s;
}
}最后再补充说明一下代码中的一个小地方，细心的小伙伴会发现，在向Queue中添加A操作和R操作的条件不一致，加入A操作时，满足边界条件即可，然而加入R操作则没有检查边界，却增加了memo的重复check。其实严谨的写法是不论A还是R，我们都需要检查边界以及memo，这样写没有任何问题。然而这里各省略一个条件的原因是，R操作只是改变速度，位置不变，不存在越界的可能，因此可以省略。另外在A操作时没有加memo重复判断的原因是，只要我们在反向时加了重复判断，保证我们不在同一个地方掉头两次，那么我们也不可定能以相同的速度加速到达某一个点2次。
本题解法用时68ms，想要学习最优解的话建议看下DP的解法。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/818-race-car-解题思路分析/