Formatted question description: https://leetcode.ca/all/818.html
818. Race Car
Level
Hard
Description
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.
Now for some target position, say 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.
Note:
1 <= target <= 10000
.
Solution
Use dynamic programming. Create an array dp
of length Math.max(target + 3, target * 2)
, where dp[i]
represents the length of the shortest sequence of instructions to get to position i
. Initialize dp[0] = 0
, dp[1] = 1
and dp[2] = 4
.
If i
is 2^k - 1
for some k
, then dp[i] = k
. Otherwise, suppose 2^(k - 1) <= i < 2^k
for some positive integer k
, it is possible to reach 2^(k - 1) - 1
first and then use instructions with “R” to reach i
, or reach 2^k - 1
first and then use instructions with “R” to reach i
. Calculate the minimum length accordingly.
class Solution {
public int racecar(int target) {
int[] dp = new int[Math.max(target + 3, target * 2)];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
dp[1] = 1;
dp[2] = 4;
for (int i = 3; i <= target; i++) {
int bits = (int) (Math.log(i) / Math.log(2)) + 1;
if (i == (1 << bits) - 1)
dp[i] = bits;
else {
for (int j = 0; j < bits - 1; j++)
dp[i] = Math.min(dp[i], dp[i - (1 << (bits - 1)) + (1 << j)] + bits - 1 + j + 2);
if ((1 << bits) - 1 - i < i)
dp[i] = Math.min(dp[i], dp[(1 << bits) - 1 - i] + bits + 1);
}
}
return dp[target];
}
}