818. Race Car

• 818. Race Car
  • Description
  • Intuition
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

这题目两个思路

1. BFS
2. DP
   1. 首先，我们denote n 为 target的总共bits数目
   2. 如果先走了n个A，那么总共走了2^n - 1
      1. 如果target正好是2^n - 1
      2. 如果不是，那么说明target∈[2^(n - 1) - 1, 2^n - 1), 那么有两种思路
         1. 走到2^n - 1，然后倒着走用recursion走完
         2. 走到2^(n - 1) - 1，然后倒着走m∈[0, n - 1)步，然后再次掉头，recursion完成剩下的步骤

            Pitfall

Solution

Reference

-Leetcode Solution -Explain of Details