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];
    }
};




Related Posts

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...