LeetCode [818] Race Car

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.

@LuckyPants/@LeetCode

https://leetcode.com/problems/race-car/discuss/123834/C%2B%2BJavaPython-DP-solution 

Consider two general cases: 

1. target == 2^i-1, this case, i is the best way
2. 2^(i-1)-1 < target < 2^i-1, there are two ways to arrive at target:
   • Use i A to arrive at 2^i-1 first, then use R to change the direction, by here there are i+1 operations (n A and one R), then the remaining is same as dp[2^i-1-target]
   • Use i-1 A to arrive at 2^(i-1)-1 first, then R to change the direction, use m A to go backward, then use R to change the direction again to move forward, by here there are i-1+2+m=i+m+1 operations (i-1 A, two R, m A) , current position is 2^(i-1)-1-(2^m-1)=2^(i-1)-2^m, the remaining operations is same as dp[target-(2^(i-1)-1)+(2^m-1)]=dp[target-2^(i-1)+2^m)].

For example:

target = 5

The right answer should be AARARAA, positions: 0, 1, 3, 3, 2, 2, 3, 5
But if we use the above formula, the answer is AA (0->3) RR (make speed at 1 again) AARA (3->5)

We can move the last A to the middle of RR, so that we save an operation. That's where the combine can happen.

So we do dp by adding m A between the RR and add the # operations for remaining distance.

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

class Solution { int dp[10001]; public: int racecar(int target) { if (dp[target] != 0) return dp[target]; int n = floor(log2(target)) + 1; if (target == pow(2, n) - 1) { dp[target] = n; } else { dp[target] = n + 1 + racecar((int)pow(2, n) - 1 - target); for (int i = 0; i < n - 1; ++i) { dp[target] = min(dp[target], racecar(target - (int)pow(2, n - 1) + (int)pow(2, i)) + i + n + 1); } } return dp[target]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { int[] dp = new int[10001]; public int racecar(int target) { if(dp[target]!=0) return dp[target]; int i = (int)(Math.log(target)/Math.log(2))+1; if(target == Math.pow(2,i)-1){ dp[target] = i; }else{ dp[target] = i+1+racecar((int)Math.pow(2,i)-1-target); for(int m=0; m<i-1; ++m){ dp[target] = Math.min(dp[target], i+1+m+racecar(target-(int)Math.pow(2, i-1)+(int)Math.pow(2, m))); } } return dp[target]; } }