# 818. Race Car

![](/files/wlZjiGxRblIHHhqbMbMv)

![](/files/OfJ7mSzhaguHLjvqkMR9)

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

S: O(2^n)

```java
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
```

```java
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)

```java
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];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/818.-race-car.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.