解法

令$A^k$Ak表示连续的k个A，容易分析出，它会在该方向上走$2^k-1$2k−1步，我们可以将最后的结果表示为$A^{k_0}RA^{k_1}...A^{k_n}R$Ak0​RAk1​...Akn​R，最后一个R可以去掉
它用数学表达式写出来就是：$(2^{k_0}-1)+(2^{k_2}-1)+...-(2^{k_1}-1)-....$(2k0​−1)+(2k2​−1)+...−(2k1​−1)−....
有个结论：

设K为target的二进制位数，那么有$target\le2^K-1$target≤2K−1
如果要超过target后再往回走，最多会走到$2^K-1$2K−1的位置，不可以再往后走了，因为假如再多走S，正向一步走了S，反向要抵消这一步需要至少$log(S)$log(S)步。

解法一：DIJSTRA

我们把图里的每个点i表示为【沿该方向向target走还差i距离】
初始为正向，那么$i=target$i=target，所以起点是dist[target]=0。
从点i可以去哪些点呢？我们由上文的分析可以知道$k_j\le K$kj​≤K，所以从点i可以通过走$2^0-1$20−1、$2^1-1$21−1、$2^2-1$22−1、…$2^K-1$2K−1步，然后再掉头，即是附加$R$R、$AR$AR、$A^2R$A2R…$A^KR$AKR，它们分别增加1、2、3、…、K+1步。
在没有加R的时候，剩余的距离为$i-(2^t-1)$i−(2t−1)，由于掉头了，那么剩余的距离变成$(2^t-1)-i$(2t−1)−i，因为要倒着走才能到target了。
所以每个点i将会联通K+1个点。

现在我们用dijstra算法，每次取步数最少的那个点$i$i，它就是真正到点i的最少步数，然后再看看从点i走的点是否能改善距离。

需要注意的是，数轴上每个整数位置都可能成为点i，这样循环就不会停了，这时候要用上上面的结论，我们的车不可能跑出$[-(2^K-1),2^K-1]$[−(2K−1),2K−1]，这就让点的个数变得有限了。

class Solution(object):
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """
        K = target.bit_length()
        up = (1<<K)-1
        from heapq import heappush,heappop
        queue = [(0,target)]
        dist = {target:0}
        while queue:
            # print queue
            d,t = heappop(queue)
            if t in dist and dist[t]<d:continue
            for k in xrange(K+1):
                d2,t2 = d+k+1,(1<<k)-1-t
                if t2==0:
                    d2-=1
                if abs(t2)<=up and (t2 not in dist or dist[t2]>d2):
                    dist[t2]=d2
                    heappush(queue,(d2,t2))
        return dist[0]

解法二：DP

令$dp[t]$dp[t]表示走t距离用的最小步数
我们走到一个target，有三种情况：

1. 如果target刚好等于$2^K-1$2K−1，那么就刚好要走K步。

2. 永远不超过这个target，走到一个位置，反回去几步，再向前走。我们一定要正向走到不能再走，即走到$2^{K-1}-1$2K−1−1处。因为：

   首先，从上面的表达式我们知道，每个$A^{k_i}R$Aki​R小节的顺序不影响结果。那么我们可以假设，下标同为偶数的$k_i$ki​是递减排列的。
   那么，此时最大的$k_0$k0​一定是K-1，否则，假如是更小的值k，从$2^k-1$2k−1到$2^{K-1}-1$2K−1−1这段距离用后面更更小的$k_i$ki​来走，肯定花费的步数更多。

   走到$2^{K-1}-1$2K−1−1处再掉头，花费K步（$A^{K-1}R$AK−1R）。然后我们需要枚举往回走j步($0\le j&lt;K-1$0≤j<K−1)再掉头，花费j+1步（$A^jR$AjR）。现在我们离target的距离缩短为$target-(2^{K-1}-1)+(2^j-1)$target−(2K−1−1)+(2j−1)，即$target-2^{K-1}+2^j$target−2K−1+2j，它要花费$dp[target-2^{K-1}+2^j]$dp[target−2K−1+2j]步，所以总花费步数为$dp[target-2^{K-1}+2^j]+K+j+1$dp[target−2K−1+2j]+K+j+1

3. 超过这个target，然后往回走。从上面的结论可知，我们最多走到$2^K-1$2K−1的位置，即花费K+1步（$A^KR$AKR）。
   然后我们就要往回走$(2^K-1)-target$(2K−1)−target距离，这个距离要花$dp[(2^K-1)-target]$dp[(2K−1)−target]步。
   总共花费的步数是$dp[(2^K-1)-target]+K+1$dp[(2K−1)−target]+K+1

综上所述，那么$dp[target]$dp[target]就在上面的所有候选者里选最小值

class Solution(object):
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """
        INF = 3*target
        f = [INF]*(target+1)
        f[0] = 0
        for t in xrange(1,target+1):
            k = t.bit_length()
            if t+1==1<<k:
                f[t]=k
                continue
            u = t-(1<<(k-1))
            for j in xrange(k-1):
                f[t]=min(f[t],f[u+(1<<j)]+k+j+1)
            if (1<<k)-t<t:
                f[t] = min(f[t],k+1+f[(1<<k)-t])
        return f[target]