#818

Race Car

candidate master · 1580 · lc hard +32 · verified · 44.6% accepted · 2,017 likes · top 27%

⚑ Linear 1D DP

Description

Your car begins at position 0 with speed +1 on an infinite number line. The car can also reach negative positions. It executes a sequence of instructions 'A' (accelerate) and 'R' (reverse):

 - Instruction 'A' causes:

 - position += speed

 - speed *= 2

 - Instruction 'R' causes:

 - If speed is positive, speed = -1

 - Otherwise, speed = 1

 Your position does not change on a reverse instruction.

For example, after instructions "AAR" the car visits positions 0 --> 1 --> 3 --> 3 with speeds 1 --> 2 --> 4 --> -1.

Given a target position target, return the length of the shortest instruction sequence that brings the car to target.

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.

Code

1
2
3