LeetCode question- Race car

Revision en2, by rr459595, 2019-08-27 11:06:27

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, return the length of the shortest sequence of instructions to get there.

Constraints:- 1<=target<=10^4


1) Input:- 3 Output:- 2 (shortest instruction is AA)

2) Input:- 6 Output:- 5 (AAARA)

3) Input:-5 Output:-7

Can someone please help me with this problem?

Thanks.

Tags #dp, #bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English rr459595 2019-08-27 11:06:27 15
en1 English rr459595 2019-08-27 11:05:24 946 Initial revision (published)