818. Race Car

Version #1 BFS with mem

Naive BFS will run at O(2^n) since for each position we have two choices: either accelerate or reverse.
Optimizations
1. To avoid duplicate search we need to keep track of searched states, however the Space will be O(2^n) -> we can only record the states that have speed +1 / -1
2. We don't accelerate once the next position has exceed the range of 2 * target

53.19 %
class Solution {
    public int racecar(int target) {
        //  BFS
        // standing at a point a[0] with speed a[1], we can either A -> new int[]{a[0] + a[1], 2 * a[1]} or new int[]{a[0], -a[1]/a[1]}
        Queue<int[]> que = new LinkedList<>();
        //state -> integer -> last bit for 0-> move backword, 1-> move forward, other bits-> position
        Set<Integer> visited = new HashSet<>();
        que.offer(new int[]{0, 1});
        visited.add(0);
        visited.add(1);
        int level = 0;
        while (!que.isEmpty()) {
            level++;
            int size = que.size();
            while (size-- > 0) {
                int[] curr = que.poll(); // curr[0]-pos, curr[1]-speed
                // System.out.println(curr[0] + curr[1]);
                if (curr[0] + curr[1] == target) {
                    return level;
                }
                // A
                if (Math.abs(curr[0] + curr[1]) < 2 * target) {
                    que.offer(new int[]{curr[0] + curr[1], 2 * curr[1]});
                }
                // R
                curr[1] = -curr[1] / Math.abs(curr[1]); // curr[1] = 4 -> -4/4=-1 curr[1] = -1 -> 4/4 = 1
                int state = (curr[0] << 1) | (curr[1] == -1 ? 0 : 1);
                // System.out.println("state " + Integer.toBinaryString(state));
                if (visited.add(state)) {
                    que.offer(new int[]{curr[0], curr[1]});
                }
            }
        }
        return -1;
    }
}