方法一：BFS
bfs所有可能的instruction，需要剪枝。
方法二：DP
定义dp[t]为以初始速度为1，向终点行进 t 所需的最小instruction数量。初始条件 dp[0]=0
Lemma：到达t的操作可以表示为 A^k1 R A^k2 R .... A^kl，我们可以重新排列，使得 k1 k2 ... kl 单调递减。
我们只考虑已经reorder以后的所有指令。根据reverse前走了几步，有三种情况
1. 刚好走了t，dp[t] = log(t+1)
2. 超过了t，我们并不知道会在哪个超过t的位置掉头。但是根据lemma，我们这一次的行进距离一定是最大的。我们只有可能 经过 n=ceiling(log(n+1)) 次连续加速，否则根本回不来。
此时掉头往回走，回头的部分即 dp[2^n-1-t]，因此 dp[t] = n (A) + 1 (R) + dp[2^n-1-t]
3. 不到t就进行了掉头。我们同样并不知道到哪就掉头了。根据lemma，我们这一次的行进距离一定是最大的。我们只有可能 经过 n-1 次连续加速，否则我们到不了t。
我们仍然不知道往回走了多少，这里需要枚举所有少于 n-1 次的加速，然后再掉头去往t。
dp[t] = min( dp[t], n-1 (A) + 1 (R) + m (A) + 1 (R) + dp[t - (2^(n-1)-2^m)] ) 0≤m<n-1
class Solution { public:vector<int> memo;int racecar(int target) {memo.resize(target+1,-1);memo[0] = 0;return f(target);}int f(int t){if (memo[t]!=-1) return memo[t];int n=ceil(log2(t+1));if (t == (1<<n)-1) return memo[t]=n;// go beyond t memo[t] = n + 1 + f((1<<n)-1-t);// not reach tfor (int m=0;m<n-1;++m){int cur = (1<<(n-1)) - (1<<m); memo[t] = min( memo[t], n-1 + 1 + m + 1 + f(t-cur) );}return memo[t];} };
时间复杂度 O(TlogT)
Reference
https://leetcode.com/problems/race-car/discuss/124326/Summary-of-the-BFS-and-DP-solutions-with-intuitive-explanation
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-818-race-car/