Race Car Problem
Description
LeetCode Problem 818.
Your 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 += speed
- speed *= 2
- When you get an instruction ‘R’, your car does the following:
- If your speed is positive then speed = -1
- otherwise speed = 1
Your position stays the same.
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:
1
2
3
4
5
Input: target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.
Example 2:
1
2
3
4
5
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 <= 10^4
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
// dp[i] is the minimum number of operations required to reach i.
// If x == 2^r - 1, the minimum number of operations is r (A^r).
// If 2^(r-1)-1 < x < 2^r - 1, there're two possibilities:
// (1) The car reaches 2^(r-1) - 1 and then reverses, accelerates
// for another A^j in the opposite direction and reverses again.
// Now its position is at 2^(r-1) - 2^j, the remaining subproblem
// is to go from current position to i with initial speed, which is dp[i-2^(r-1)+2^j].
// (2) The car reaches 2^r - 1 and reverses, the remaining subproblem is equal to dp[2^r-1-i].
int racecar(int target) {
vector<int> dp(target+1, INT_MAX);
int r = 1;
for (int i = 1; i <= target; i++) {
if (i == pow(2,r)-1) {
dp[i] = r;
r++;
}
else {
int lower = pow(2, r-1)-1;
int upper = pow(2, r)-1;
for (int j = 0; j < r-1; j++) {
dp[i] = min(dp[i], r+1+j+dp[i-pow(2,r-1)+pow(2,j)]);
}
dp[i] = min(dp[i], r+1+dp[upper-i]);
}
}
return dp[target];
}
};