818. Race Car

T: O(2^n) since for each position we have two choices: either accelerate or reverse

S: O(2^n)

class Solution {
    public int racecar(int target) {
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new ArrayDeque<>(); // position, speed
        queue.offer(new int[]{0,1});
        visited.add(Arrays.toString(new int[]{0,1}));
        
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                if (curr[0] == target) {
                    return res;
                }
                
                int[] instructionA = new int[]{curr[0]+curr[1], curr[1]*2};
                String stateA = Arrays.toString(instructionA);
                
                if (instructionA[0] >= 0 && !visited.contains(stateA)) {
                    queue.offer(instructionA);
                    visited.add(stateA);
                }
                
                int[] instructionR = new int[]{curr[0], curr[1] > 0 ? -1 : 1};
                String stateR = Arrays.toString(instructionR);
                
                if (instructionR[0] >= 0 && !visited.contains(stateR)) {
                    queue.offer(instructionR);
                    visited.add(stateR);
                }
            }
            res++;
        }
        return -1;
    }
}


/*
BFS solution

position += speed
speed *= 2

has A R two ways to arrive Destination

shortest => BFS, or DP
return the length of the shortest sequence of instructions

Set<String> visited
new int{position, speed}

in 
BFS 
, if new int[p, s], p = target return res;

cal A state if legal put into queue

cal R state if legal put into queue

T: O(2^n) since for each position we have two choices: either accelerate or reverse
S: O(2^n)
*/

其中如果限制了這部分, 可以加快速度, 因為如果今天不小心超過 target 太多時, 其實是不合理的, 要倒車很多次

所以有一個界線會有差 可以 target*1.5 ～ target*2

我認為是因為每次增加都是 2的次方倍數速度增加, 所以不小心超過時, 1.5倍應該是可以容許的範圍

if (instructionA[0] >= 0 && instructionA[0] <。target*1.5

if (instructionR[0] >= 0 && instructionR[0] < target*1.5

class Solution {
    public int racecar(int target) {
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new ArrayDeque<>(); // position, speed
        queue.offer(new int[]{0,1});
        visited.add(Arrays.toString(new int[]{0,1}));
        
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                if (curr[0] == target) {
                    return res;
                }
                
                int[] instructionA = new int[]{curr[0]+curr[1], curr[1]*2}; // // position, speed
                String stateA = Arrays.toString(instructionA);
                
                if (instructionA[0] >= 0 && instructionA[0] < target*1.5 && !visited.contains(stateA)) {
                    queue.offer(instructionA);
                    visited.add(stateA);
                }
                
                int[] instructionR = new int[]{curr[0], curr[1] > 0 ? -1 : 1};
                String stateR = Arrays.toString(instructionR);
                
                if (instructionR[0] >= 0 && instructionR[0] < target*1.5 && !visited.contains(stateR)) {
                    queue.offer(instructionR);
                    visited.add(stateR);
                }
            }
            res++;
        }
        return -1;
    }
}

DP - 最優解

T: O(n * (logn)^2 ), n is target

S: O(n)

class Solution {
    public int racecar(int target) {
        int[] dp = new int[target+1];
        
        
        for (int i = 1; i <= target; i++) {
            dp[i] = Integer.MAX_VALUE;
            int j = 1; 
            int cnt1 = 1; // 正向（A）走需要的 instructions 次數, pos j = 1, mean 走一次了
            // cnt2 反向（R）走需要的 instructions 次數
            for (; j < i; j = (1 << ++cnt1)-1) {
                for (int k = 0, cnt2 = 0; k < j; k = (1 << ++cnt2)-1) {
                    dp[i] = Math.min(dp[i], cnt1 + 1 + cnt2 + 1 + dp[i - (j-k)]);
                }
            }
            dp[i] = Math.min(dp[i], cnt1 + (j == i ? 0 : dp[j-i]+1));
        }
        return dp[target];
    }
}