818. Race Car.md

818. Race Car

---

Difficulty : Hard

Related Topics : Dynamic Programming、Heap

---

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.

---

Solution

• mine
  • Java
    • got from the most votes Runtime: 2 ms, faster than 91.08%, Memory Usage: 40.3 MB, less than 47.06% of Java online submissions

      // O(T * logT)time
      // O(T)space
      int[] dp = new int[10001];
      
      public int racecar(int target) {
          if (dp[target] > 0) return dp[target];
          int n = (int) (Math.log(target) / Math.log(2)) + 1;
          if (1 << n == target + 1) {
              dp[target] = n;
          } else {
              //n times A
              int dis = (1 << n) - 1;
              // n + 1 =  N times A + R
              dp[target] = racecar(dis - target) + n + 1;
      
              // n - 1 times A
              int pre = 1 << (n - 1);
              for (int m = 0; m < n - 1; m++) {
                  // n-1 times A + R + m times A  + R + racecar(target - pre + (1 << m))
                  dp[target] = Math.min(dp[target], racecar(target - pre + (1 << m)) + n + m + 1);
              }
          }
          return dp[target];
      }
      

---

• the most votes

• DP Runtime: 2 ms, faster than 91.08%, Memory Usage: 40.3 MB, less than 47.06% of Java online submissions

  // O(T * logT)time
  // O(T)space
  int[] dp = new int[10001];
  public int racecar(int t) {
      if (dp[t] > 0) return dp[t];
      int n = (int)(Math.log(t) / Math.log(2)) + 1;
      if (1 << n == t + 1) {
          dp[t] = n;
      } else {
          dp[t] = racecar((1 << n) - 1 - t) + n + 1;
          for (int m = 0; m < n - 1; ++m) {
              dp[t] = Math.min(dp[t], racecar(t - (1 << (n - 1)) + (1 << m)) + n + m + 1);
          }
      }
      return dp[t];
  }
  

---

• leetcode solution

• Runtime: 3 ms, faster than 88.11%, Memory Usage: 36.7 MB, less than 67.65% of Java online submissions

  // O(T * logT)time
  // O(T)space
  public int racecar(int target) {
      int[] dp = new int[target + 3];
      Arrays.fill(dp, Integer.MAX_VALUE);
      dp[0] = 0; dp[1] = 1; dp[2] = 4;
  
      for (int t = 3; t <= target; ++t) {
          int k = 32 - Integer.numberOfLeadingZeros(t);
          if (t == (1<<k) - 1) {
              dp[t] = k;
              continue;
          }
          for (int j = 0; j < k-1; ++j)
              dp[t] = Math.min(dp[t], dp[t - (1<<(k-1)) + (1<<j)] + k-1 + j + 2);
          if ((1<<k) - 1 - t < t)
              dp[t] = Math.min(dp[t], dp[(1<<k) - 1 - t] + k + 1);
      }
  
      return dp[target];
  }
  

---