[LeetCode]818. Race Car｜BFS & DP附图详解(JavaScript版)
题目描述
LeetCode原题链接：818. Race CarYour car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):
- When you get an instruction
'A', your car does the following:position += speedspeed *= 2
- When you get an instruction
'R', your car does the following:- If your speed is positive then
speed = -1 - otherwise
speed = 1
- If your speed is positive then
For example, after commands AAR, your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.
Given a target position target, return the length of the shortest sequence of instructions to get there.
Example 1:
Input: target = 3 Output: 2 Explanation: The shortest instruction sequence is AA. Your position goes from 0 --> 1 --> 3.
Example 2:
Input: target = 6 Output: 5 Explanation: The shortest instruction sequence is AAARA. Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.
Constraints:
1 <= target <= 104
解法一：BFS + 剪枝
找最小值的一个很容易想到的办法就是BFS广度优先遍历。对于任意一个位置，我们可以有accelerate和reverse两种操作。那么我们就从起始位置开始穷举这两种操作的所有可能的排列组合到达的位置，直到小车前进到target位置为止。
1 var racecar = function(target) { 2 let queue = [[0, 1]]; 3 let step = 0; 4 while(queue.length) { 5 let len = queue.length; 6 while(len-- > 0) { 7 let cur = queue.shift(); 8 let position = cur[0], speed = cur[1]; 9 if(position == target) return step; 10 11 // accelerate 12 queue.push([position + speed, speed * 2]); 13 14 // reverse 15 queue.push([position, speed > 0 ? -1 : 1]); 16 } 17 step++; 18 } 19 return -1; 20 }; 显然，这种方法肯定超时无疑了。为了避免重复运算，我们可以用一个set来保存已经出现过的状态。注意，这里的状态包括position和speed两个变量，不像常规的BFS只去记录位置一个信息（因为下一位置取决于当前位置和当前速度，即使之后又返回到同一位置，如果速度不一样的话还是会导致不同的结果）。方便起见，可以将当前位置和当前速度连接成一个string作为key存入set中。
1 var racecar = function(target) { 2 let queue = [[0, 1]]; 3 let visited = new Set(); 4 let step = 0; 5 while(queue.length) { 6 let len = queue.length; 7 while(len-- > 0) { 8 let cur = queue.shift(); 9 let position = cur[0], speed = cur[1]; 10 if(position == target) return step; 11 12 let key = position + , + speed; 13 if(visited.has(key)) continue; // skip duplicated status 14 visited.add(key); 15 16 // accelerate 17 queue.push([position + speed, speed * 2]); 18 19 // reverse 20 queue.push([position, speed > 0 ? -1 : 1]); 21 } 22 step++; 23 } 24 return -1; 25 }; 相比于无脑列举所有情况，使用set去重后，test case通过率从32/55变成了48/55。我们还可以在哪优化呢？
抛开上面的问题，我们先来看个规律：
对于加速操作，position和speed的关系如下:
#0 (initial) --> position: 0 speed: 1
#1 --> position: 1 speed: 2
#2 --> position: 3 speed: 4
#3 --> position: 7 speed: 8
#4 --> position: 15 speed: 16
#5 --> position: 31 speed: 32
......
发现了吗，如果连续加速的次数为n次的话，postion=2^n-1。而对于反转操作，如果把正负号视为方向的话，那么该操作就是反转小车移动方向后重新将speed赋值为初始值1。
当然，小车肯定不能无限连续加速，否则在超过target之后如果仍然保持加速的话会距目标位置越来越远。但是如果在超过目标位置之后的某一范围内及时调头还是有可能再重新回到target的。这个“一定范围”就是我们的剪枝标准，即当前小车到达的位置postion的上限是哪里？
进一步来说，这个一定范围的临界点是哪里呢？如果小车的某一次移动使其从target左边跑到了右边，即超过了target，那么此时我们应立即掉头才能确保最终结果最小（并不是说如果已经超过了target再向前加速到某一位置时才掉头就不能回到目标位置了，只是这种情况下最终结果肯定不是最优解）。现在就让我们来模拟这个临界状态：
假设小车即将超过target前连续加速了n次，则到达的位置为position=2^n-1<target，此时的speed=2^n；又因为target是一个整数，所以我们可以认为target=2^n+k，其中k>=0。
那么小车到达的下一位置即超过target的位置则为nextPosition=position+speed=(2^n-1)+2^n=2*2^n-1=2*(target-k)-1=2*target-(2*k+1)，又k>=0，所以2*k+1>=1，那么整个表达式2*target-(2*k+1)一定小于2*target，即nextPosition<2*target。
好了，一定范围找到了，如果当前到达的位置>=2*target的话就不用考虑了，因为那样就算最终能回到目标位置肯定不是最优解。于是我们的BFS就能优化为：
1 var racecar = function(target) { 2 let queue = [[0, 1]]; 3 let visited = new Set(); 4 visited.add(0,1); 5 let step = 0; 6 while(queue.length) { 7 let len = queue.length; 8 while(len-- > 0) { 9 let cur = queue.shift(); 10 let position = cur[0], speed = cur[1]; 11 if(position == target) return step; 12 13 // accelerate 14 let next = [position + speed, speed << 1]; 15 let key = next.toString(); 16 if(!visited.has(key) && 0 < next[0] && next[0] < (target << 1)) { 17 visited.add(key); 18 queue.push(next); 19 } 20 21 // reverse 22 next = [position, speed > 0 ? -1 : 1]; 23 key = next.toString(); 24 if(!visited.has(key) && 0 < next[0] && next[0] < (target << 1)) { 25 visited.add(key); 26 queue.push(next); 27 } 28 } 29 step++; 30 } 31 return -1; 32 }; 终于，通过所有test case了，虽然有点慢哈哈哈哈...
解法二：动态规划
在解法一中我们罗列了一种情况，那就是一旦超过target就立即回头；其实我们也可以在未到达target之前就回头，倒退几步后再回头，然后驶向目标位置。
当然，还有一种理想情况是第一次连续加速后就能恰好到达target位置：
我们用dp[cur]来表示小车从起始位置到达cur位置时的最小操作个数。注意这里对dp数组每一项含义的定义：从起始位置（position=0, speed=1状态）到达终点cur（position=cur）位置时的最小操作数，即小车行驶cur距离时的最小操作数。前面提到，一旦小车发生掉头操作，实质就是换了个方向又重新回到起始状态。也就是说反转后的小车在某一位置（非position=0位置）的最小操作数也可以用dp来表示，这个时候需要把转向点作为起点：
不难发现，其实我们关心的是从起始位置（可以是position=0，也可以是坐标上任意一点）到终点位置小车移动的距离，位置的描述可能会产生歧义，下面的分析我们全部用移动的距离来表示position，即dp[cur]表示小车从Math.abs(speed)=1状态移动cur距离时最小操作数。
对于reverse操作，我们很显然可以根据图示直观得到结果：...ARA...中需要一次掉头操作，...ARARA...中需要两次两次掉头操作；但问题的关键是我们不知道需要经过几次accelerate操作才能转向，所以我们需要尝试所有可能的操作：加速0次、加速1次、加速2次、加速3次......根据解法一中的分析我们知道，如果连续加速n次，到达的位置即行驶的距离为2^n-1。无论哪种情况，小车第一段操作均是连续加速（题目中限制了target>=1，而起始位置为position=0，所以说至少要进行一次加速操作），然后根据连续加速后移动的距离和target的关系（是否超过了target）才衍生出三种子情况。假设第一段连续加速的次数为cnt1，那么到达的第一个转向点时小车经过了r1=2^cnt1-1，且cnt1>=1，从起始状态(position=0, speed=1)加速一次，小车移动的距离为1，因此循环语句的初始条件为r1=1, cnt1=1。
let r1 = 1, cnt1 = 1; // first continous acceleration while(r1 < cur) { // ... r1 = Math.pow(2, ++cnt1) - 1; } 其中，cur表示小车当前移动的距离。分别来处理不同的三种情况：
-
case 1: r1 < cur
掉头之后再到达第二个转向点之前，我们仍然不知道需要经历几次加速操作，因此仍需尝试所有可能的操作，假设第二段连续加速的次数为cnt2，那么到达的第二个转向点时行驶的距离就是r2=2^cnt2-1，这里的cnt2可以取0，对应的是第一次掉头后原地不动立刻又二次掉头的情况，所以cnt2>=0。同理，该段内是背离r1方向行驶的，要想得到最优解需确保r2不能超过r1，也就是说第二段连续加速的最远距离要小于r1。这两个阶段分别需要cnt1+cnt2次A操作，和两次R操作，即cnt1+1+cnt2+1次操作，然后此时小车将直接加速驶终点cur；前两段一段正向移动，一段反向移动，所以总共正向移动了r1-r2距离，那么距离终点cur还有cur-(r1-r2)距离，这一移动距离的最小操作数为dp[cur-(r1-r2)]，则我们可以得到这一情况下状态转移方程为 dp[cur]=cnt1+1+cnt2+1+dp[cur-(r1-r2)]
1 let r1 = 1, cnt1 = 1; // first continous acceleration 2 while(r1 < cur) { 3 let r2 = 0, cnt2 = 0; // second continous acceleration 4 while(r2 < r1) { 5 dp[cur] = Math.min(dp[cur], cnt1 + 1 + cnt2 + 1 + dp[cur - (r1 - r2)]); 6 r2 = Math.pow(2, ++cnt2) - 1; 7 } 8 r1 = Math.pow(2, ++cnt1) - 1; 9 } -
case 2: r1 > cur
该情况下小车在超过终点后立刻掉头，掉头后就直接驶回终点。上面代码第2行的while循环break的时候，就是r1刚刚超过cur的时候，正好符合case2的状态，所以我们可以认为第2行break之后的cnt1和r1就是case2中第一段移动结束后的状态。图中第二段总共移动的距离为r1-cur，这一移动距离下的最小操作数为dp[r1-cur]，加上第一段的操作数cnt1+1（1为一次R操作），所以总共的移动次数即该情况下状态转移方程为 dp[cur]=cnt1+1+dp[r1-cur]
-
case 3: r1 = cur
第一段连续加速恰好到达目标位置，此时最短操作数就是cnt1，该情况下状态转移方程为 dp[cur]=cnt1
1 let r1 = 1, cnt1 = 1; // first continous acceleration 2 while(r1 < cur) { 3 let r2 = 0, cnt2 = 0; // second continous acceleration 4 while(r2 < r1) { 5 // case1: ...ARARA... 6 dp[cur] = Math.min(dp[cur], cnt1 + cnt2 + 2 + dp[cur - (r1 - r2)]); 7 r2 = Math.pow(2, ++cnt2) - 1; 8 } 9 r1 = Math.pow(2, ++cnt1) - 1; 10 } 11 if(cur == r1) { 12 // case3: after first continous acceleration, the car just arrives at the end pos 13 dp[cur] = Math.min(dp[cur], cnt1); 14 } 15 else { 16 // case2: ...ARA... 17 dp[cur] = Math.min(dp[cur], cnt1 + 1 + dp[r1 - cur]); 18 } 最终的dp[cur]应当是这三种情况下的最小值。题目中限制了target>=1，所以我们cur从1开始遍历到target结束就可以了。最终的结果就是dp[target]，完整的dp解法示例代码如下：
1 var racecar = function(target) { 2 let dp = new Array(target + 1); 3 for(let cur = 1; cur <= target; cur++) { 4 dp[cur] = Number.MAX_VALUE; 5 let r1 = 1, cnt1 = 1; // first continous acceleration 6 while(r1 < cur) { 7 let r2 = 0, cnt2 = 0; // second continous acceleration 8 while(r2 < r1) { 9 // case1: ...ARARA... 10 dp[cur] = Math.min(dp[cur], cnt1 + cnt2 + 2 + dp[cur - (r1 - r2)]); 11 r2 = Math.pow(2, ++cnt2) - 1; 12 } 13 r1 = Math.pow(2, ++cnt1) - 1; 14 } 15 16 // if(cur == r1) { 17 // // case3: after first continous acceleration, the car just arrives at the end pos 18 // dp[cur] = Math.min(dp[cur], cnt1); 19 // } 20 // else { 21 // // case2: ...ARA... 22 // dp[cur] = Math.min(dp[cur], cnt1 + dp[r1 - cur] + 1); 23 // } 24 25 // simplify 26 dp[cur] = Math.min(dp[cur], cnt1 + (cur == r1 ? 0 : dp[r1 - cur] + 1)); 27 } 28 return dp[target]; 29 };