# 818. Race Car

初始位置为0，速度为1，每步可以速度\*2, 或者调头并把速度置为1，问最后到target所需最少步数。最小步数问题用BFS或DP。BFS需要做一些剪枝，比如visited只存speed为1或-1的key = pos\_speed，虽然会重复走，但会大规模减少visited的size，从而降低检索时间；还有当距离为target两倍时，终止继续遍历。DP则把对每个距离i, 遍历所有可能性，主要是两种: 1. 加速到j, （调两次头）速度重置回1，再加速到k位置，对剩下的i - (j-k)距离用子问题求解; 2. 一直加速到刚好超过i的位置，然后回头到i。看上去k的那个循环仿佛是多余的，但其实是需要的，在对j做循环时不能直接用dp\[i - j]，原因我目前也不知道。

答案参考了[这](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/grandyang/p/10360655.html%23commentform)。

```cpp
/*
 * @lc app=leetcode id=818 lang=cpp
 *
 * [818] Race Car
 */
class Solution {
public:
    int racecar(int target) {
       vector<int> dp(target + 1);
       for (int i = 1; i <= target; ++i) {
           dp[i] = INT_MAX; // 跑完i距离需要的最短步数
           int j = 1, cnt1 = 1;
           // 正向不断加速到i前的每个可能的j位置(最远到2^N - 1)
           for (; j < i; j = (1 << ++cnt1) - 1) {
               // 调头再调回来让速度reset回1，不断正向加速到k位置, 再解决子问题: 跑(i - (j - k))需要的最少步数
               for (int k = 0, cnt2 = 0; k < j; k = (1 << ++cnt2) - 1) {
                   dp[i] = min(dp[i], cnt1 + 1 + cnt2 + 1 + dp[i - (j - k)]);
               }
           }
           // 此时j所在为刚好正向跑过i, 再回头跑到i
           dp[i] = min(dp[i], cnt1 + (i == j ? 0 : 1) + dp[j - i]);
       } 
       return dp[target];
    }
};


```