# 0818. Race Car
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/race-car/
## 思路
参考[这里](https://leetcode.com/problems/race-car/discuss/123834/JavaC%2B%2BPython-DP-solution)
有两个方法能到target点
Let's say ```n``` is the length of target in binary and we have ```2^(n - 1) <= target < 2^n```
1. **Go pass our target , stop and turn back** 走n步超过target点 再用一个R折返 走回target
2. **Go as far as possible before pass target, stop and turn back** 走n-1步 再用一个R折返 接着往反方向走m步 再转向走回target
## Code

class Solution {
    int[] dp = new int[10001];
    public int racecar(int target) {
        if(dp[target]!=0) return dp[target];
        int n = (int)(Math.log(target)/Math.log(2))+1;
        if(target+1==1<<n) return dp[target]=n;
        dp[target] = racecar((1<<n)-target-1)+1+n;
        for(int m=0; m<n-1; m++){
            dp[target] = Math.min(dp[target], racecar(target-(1<<(n-1))+(1<<m))+n+m+1);
        }
        return dp[target];
    }
}