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.
static int[][] dp = new int[10001][2];
public int racecar(int k) {
if(dp[k][0] == 0) {
for(int target = 1; target < dp.length; target++) {
int n = 0;
while((1 << n)-1 < target) n++;
if((1 << n)-1 == target) {
dp[target][0] = n;
dp[target][1] = n+1;
continue;
}
int remain = (1 << n)-1 - target;
dp[target][0] = n + 1 + Math.min(dp[remain][1], dp[remain][0]+1);
dp[target][1] = n + 1 + Math.min(dp[remain][0], dp[remain][1]+1);
for(int i = 1; i < target; i++) {
dp[target][0] = Math.min(dp[target][0], Math.min(dp[i][0] + 2 + dp[target-i][0], dp[i][1] + 1 + dp[target-i][0]));
dp[target][1] = Math.min(dp[target][1], Math.min(dp[i][0] + 2 + dp[target-i][1], dp[i][1] + 1 + dp[target-i][1]));
}
}
}
return Math.min(dp[k][0], dp[k][1]);
}
class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
public int racecar(int target) {
return dp(target);
}
public int dp(int target) {
if(map.containsKey(target)) return map.get(target);
int n = 0;
while((1 << n)-1 < target) n++;
if((1 << n)-1 == target) {
return n;
}
int result = n + 1 + dp((1 << n)-1 - target);
// A(n), R, dp
for(int i = 0; i < n-1; i++) {
result = Math.min(result, n - 1 + 1 + i + 1 + dp(target - (1 << (n-1)) + (1 << i)));
//A(n-1), R，A(i),R + dp
}
map.put(target, result);
return result;
}
}