818. Race Car

Question

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 = 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.

Solutions:

Method 1: bfs O(2 ^ N), where n is the maximum target.

for each action, it could be A or R.

According to Huahua’s assumption, I used assumption “pos < target * 2”.

class Solution {
  public int racecar(int target) {
      LinkedList<int[]> queue = new LinkedList<>();
      // int[2]: index 0: pos and index 1: speed
      queue.offer(new int[]{0, 1});
      int step = 0;
      Set<String> visited = new HashSet<>();
      while(!queue.isEmpty()){
          int size = queue.size();
          ++step;
          for(int i = 0; i < size; i++){
              int[] cur = queue.poll();
              // 1. If next action is A.
              int posA = cur[0] + cur[1];
              if(posA == target) return step;
              int speA = cur[1] * 2;
              String keyA = posA + "_" + speA;
              if(posA < target * 2){
                  queue.offer(new int[]{posA, speA});
              }
              // 2. If next action is R.
              int speB = cur[1] > 0 ? -1: 1;
              String keyB = cur[0] + "_" + speB;
              if(visited.contains(keyB)) continue;
              visited.add(keyB);
              queue.offer(new int[]{cur[0], speB});
          }
      }
      return -1;
  }
}

Method 2: dp

class Solution {
    private static int[][] dp;
    public int racecar(int target) {
        if(dp == null){
            dp = new int[10001][2];
            // dp[i][d] means mminimal step reaching position i
            // d == 0 means we are facing target
            // d == 1 means we are facing original point.
            for(int t = 0; t <= 10000; t++){
                int n = (int)Math.ceil(Math.log(t + 1) / Math.log(2));
                if(t + 1 == 1 << n){
                    dp[t][0] = n;
                    dp[t][1] = n + 1;
                    continue;
                }
                int rest = (1 << n) - 1 - t;
                dp[t][0] = n + 1 + Math.min(dp[rest][1], dp[rest][0] + 1);
                dp[t][1] = n + 1 + Math.min(dp[rest][0], dp[rest][1] + 1);
                for(int i = 0; i < t; i++){
                    for(int d = 0; d < 2; d++){
                        dp[t][d] = Math.min(dp[t][d], Math.min(
                        dp[i][0] + 2 + dp[t - i][d],
                        dp[i][1] + 1 + dp[t - i][d]));
                    }
                }
            }
        }
        return Math.min(dp[target][0], dp[target][1]);
    }
}

Reference

花花酱 LeetCode 818. Race Car