Race Car
Problem
A car starts at 0 with speed +1. 'A' doubles speed and moves; 'R' flips direction and resets speed to +/-1. Return the minimum length instruction sequence to reach target.
target = 32def racecar(target):
dp = [0, 1, 4] + [0] * (target - 2)
for t in range(3, target + 1):
n = t.bit_length()
if (1 << n) - 1 == t:
dp[t] = n
continue
best = n + 1 + dp[(1 << n) - 1 - t]
for m in range(n - 1):
best = min(best, n - 1 + m + 2 + dp[t - (1 << (n-1)) + (1 << m)])
dp[t] = best
return dp[target]var racecar = function(target) {
const dp = new Array(target + 1).fill(0);
dp[1] = 1; if (target >= 2) dp[2] = 4;
for (let t = 3; t <= target; t++) {
const n = 32 - Math.clz32(t);
if ((1 << n) - 1 === t) { dp[t] = n; continue; }
let best = n + 1 + dp[(1 << n) - 1 - t];
for (let m = 0; m < n - 1; m++) {
best = Math.min(best, n - 1 + m + 2 + dp[t - (1 << (n-1)) + (1 << m)]);
}
dp[t] = best;
}
return dp[target];
};class Solution {
public int racecar(int target) {
int[] dp = new int[target + 1];
dp[1] = 1; if (target >= 2) dp[2] = 4;
for (int t = 3; t <= target; t++) {
int n = 32 - Integer.numberOfLeadingZeros(t);
if ((1 << n) - 1 == t) { dp[t] = n; continue; }
int best = n + 1 + dp[(1 << n) - 1 - t];
for (int m = 0; m < n - 1; m++) {
best = Math.min(best, n - 1 + m + 2 + dp[t - (1 << (n-1)) + (1 << m)]);
}
dp[t] = best;
}
return dp[target];
}
}class Solution {
public:
int racecar(int target) {
vector<int> dp(target + 1, 0);
dp[1] = 1; if (target >= 2) dp[2] = 4;
for (int t = 3; t <= target; t++) {
int n = 32 - __builtin_clz(t);
if ((1 << n) - 1 == t) { dp[t] = n; continue; }
int best = n + 1 + dp[(1 << n) - 1 - t];
for (int m = 0; m < n - 1; m++) {
best = min(best, n - 1 + m + 2 + dp[t - (1 << (n-1)) + (1 << m)]);
}
dp[t] = best;
}
return dp[target];
}
};Explanation
The car speeds up by doubling with each A (covering 1, 2, 4, 8, ...) and can flip direction with R. We solve dp[t] = the fewest instructions to land exactly on position t, building from smaller targets up.
The neat fact is that n consecutive A's carry you exactly to 2ⁿ - 1. So if the target itself equals 2ⁿ - 1, you just press A n times and dp[t] = n.
Otherwise there are two strategies. Overshoot: go past the target to 2ⁿ - 1 with n A's, reverse, and solve the leftover distance — that costs n + 1 + dp[(2ⁿ-1) - t]. Undershoot: stop one step early with n-1 A's, reverse, drive back a bit with m A's, reverse again, then solve the remaining gap. We try every m and keep the cheapest.
Example: target = 3. Here 3 = 2² - 1, so two A's ("AA") drive 0 → 1 → 3 and the answer is 2.
Because each target only tries about log-many reverse points, the whole table fills in O(target · log target) time.