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.

// BFS
int racecar(int target) { // time: O(target * log(target)); space: O(target * log(target))
    int res = 0;
    queue<pair<int, int> > q({{0, 1}}); // pair<position, speed>
    unordered_set<string> visited({"0_1"});
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            int pos = q.front().first, speed = q.front().second;
            q.pop();
            if (pos == target) return res;
            // Acceleration
            int new_pos = pos + speed, new_speed = speed * 2;
            string encode_str = to_string(new_pos) + "_" + to_string(new_speed);
            if (!visited.count(encode_str) && new_pos > 0 && new_pos < 2 * target) {
                visited.insert(encode_str);
                q.push({new_pos, new_speed});
            }
            // Reverse
            new_pos = pos;
            new_speed = (speed > 0) ? -1 : 1;
            encode_str = to_string(new_pos) + "_" + to_string(new_speed);
            if (!visited.count(encode_str) && new_pos > 0 && new_pos < 2 * target) {
                visited.insert(encode_str);
                q.push({new_pos, new_speed});
            }
        }
        ++res;
    }
    return -1;
}

// Top-Down Dynamic Programming
int helper(int i, vector<int>& dp) {
    if (dp[i] >= 0) return dp[i];
    dp[i] = numeric_limits<int>::max();
    int j = 1, m = 1;
    // Consider the case j < i then reverse directly after continuous m acceleration
    // Then reverse again after continuous acceleration (p is the reverse distance after the first reverse)
    for (; j < i; j = (1 << ++m) - 1) {
        for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
            dp[i] = min(dp[i], m + 1 + q + 1 + helper(i - (j - p), dp) );
        }
    }
    // Consider the case j == i or j > i then reverse
    dp[i] = min(dp[i], m + (j == i ? 0 : 1 + helper(j - i, dp) ) );
    return dp[i];
}
int racecar(int target) { // time: O(target * (log(target))^2); space: O(target)
    vector<int> dp(target + 1, -1);
    dp[0] = 0;
    return helper(target, dp);
}

// Bottom-Up Dynamic Programming
int racecar(int target) { // time: O(target * (log(target))^2); space: O(target)
    vector<int> dp(target + 1, 0);
    for (int i = 1; i <= target; ++i) {
        dp[i] = numeric_limits<int>::max();
        int j = 1, m = 1;
        // Consider the case j < i then reverse directly after continuous m acceleration
        // Then reverse again after continuous acceleration (p is the reverse distance after the first reverse)
        for (; j < i; j = (1 << ++m) - 1) {
            for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
                dp[i] = min(dp[i], m + 1 + q + 1 + dp[i - (j - p)]);
            }
        }
        // Consider the case j == i or j > i then reverse
        dp[i] = min(dp[i], m + (j == i ? 0 : 1 + dp[j - i]));
    }
    return dp.back();
}