818. Race Car

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.

---------------------------

Solution #1, BFS 暴解，内存不不够 case: 330

O(2^n)

class Solution {
    public int racecar(int target) {
        Queue<Node> que = new LinkedList<>();
        Node root = new Node(0, 1, 0);
        que.add(root);
        
        while (!que.isEmpty()) {
            Node node = que.poll();
            if (node.pos == target) return node.len;
            que.add(new Node(node.pos + node.speed, node.speed * 2, node.len + 1));
            que.add(new Node(node.pos, node.speed > 0 ? -1 : 1, node.len + 1));
        }
        
        return 0;
    }
    
    class Node{
        public int pos;
        public int speed;
        public int len;
        public Node(int pos, int speed, int len) {
            this.pos = pos;
            this.speed = speed;
            this.len = len;
        }
    }
}

Solution #2, 加了优化 关键在于剪枝：Math.abs(nextPos - target) <= target. 因为起点跟target的距离就是target，如果比这个还远的话，那最终的步数肯定会超过，没有意义，所以要略掉O (n * log n), n为target的⼤小。速度只有log n种可能，因为速度永远是2的幂次⽅ O(n * log n) 空间，最坏情况是把所有pos和speed的组合都放在queue⾥

class Solution {
    public int racecar(int target) {
        Queue<Node> que = new LinkedList<>();
        Node root = new Node(0, 1, 0);
        que.add(root);
        Set<String> visited = new HashSet<>();
        visited.add("0#1");
        visited.add("0#-1");
        
        while (!que.isEmpty()) {
            Node node = que.poll();
            if (node.pos == target) return node.len;
            int nextPos = node.pos + node.speed;
            String key1 = nextPos  + "#" + node.speed *2;
            if (!visited.contains(key1) && Math.abs(nextPos - target) <= target) {
                que.add(new Node(nextPos, node.speed * 2, node.len + 1));
                visited.add(key1);                
            }
                
            String key2 = node.pos + "#" + (node.speed > 0 ? -1 : 1);
            if (!visited.contains(key2)) {
                que.add(new Node(node.pos, node.speed > 0 ? -1 : 1, node.len + 1));
                visited.add(key2);
            }
        }
        
        return 0;
    }
    
    class Node{
        public int pos;
        public int speed;
        public int len;
        public Node(int pos, int speed, int len) {
            this.pos = pos;
            this.speed = speed;
            this.len = len;
        }
    }
}

Solution #3 rec + memoiz1tion 暴力枚举。 分3种情况：

1. 刚好⾛到，target == pos，target刚好是2的幂次⽅
2. 走过头一步，target < pos (两步就没有必要了，看Solution#2的剪枝) 
3. ⾛i步回头, 再⾛j步回头, i 属于[0, target], j 属于 [0, target - pos]. 注意变量的取值 

ref: https://leetcode.com/problems/r1ce-c1r/discuss/124326/Summ1ry-of-the-BFS-1nd-DP-solutions-with-intuitive-expl1n1tion

class Solution {
    public int racecar(int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, - 1);
        dp[0] = 0;
        return dfs(target, dp);
    }
    
    private int dfs(int target, int[] dp) {
        if (dp[target] >= 0) return dp[target];
        
        dp[target] = Integer.MAX_VALUE;
        int speed = 1, pos = 0, times = 0;
        for (; pos < target; pos += speed, speed <<= 1, times++) {
            
            for (int revPos = 0, revSpeed = 1, revTimes = 0; revPos < pos; revPos += revSpeed, revSpeed <<= 1, revTimes++) {
                dp[target] = Math.min(dp[target], times + 2 + revTimes + dfs(revPos + target - pos, dp));
            }
        }
        
        if (target == pos) {
            dp[target] = Math.min(dp[target], times);    
        }else {
            dp[target] = Math.min(dp[target], times + 1 + dfs(pos - target, dp));
        }
        
        return dp[target];
    }
}

Solution #4 iterative的⽅法，ToDo