https://leetcode.com/problems...
Hard
Google, Amazon
第一种解法应用BFS
// bfspublic int racecar(int target) { int res = 0; Queue<int[]> q = new LinkedList<>(); // 0: position, 1: speed Set<String> visited = new HashSet<>(); visited.add("0#1"); q.offer(new int[]{0, 1}); while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { int[] cur = q.poll(); assert cur != null; int pos = cur[0], speed = cur[1]; if (pos == target) return res; // 指标地位，间接返回res // 1. 尝试减速，更新新地位，新速度 int newPos = pos + speed, newSpeed = speed * 2; String key = newPos + "#" + newSpeed; if (!visited.contains(key) && newPos > 0 && newPos < target * 2) { visited.add(key); q.offer(new int[]{newPos, newSpeed}); } // 2. 尝试转向，地位不变，速度依据正负数变成1或者-1 newPos = pos; newSpeed = speed > 0 ? -1 : 1; key = newPos + "#" + newSpeed; if (!visited.contains(key) && newPos > 0 && newPos < target * 2) { visited.add(key); q.offer(new int[]{newPos, newSpeed}); } } res++; } return -1;}第二种解法，DP
dp[target] 示意行驶长度为target的间隔须要的最小批示个数。dp[target]有两种可能：
- target刚好是由"AAA...A"一共n步达到，也就是一路减速，那么这种走法就是最优抉择。
- 如果不是上述情况，就有多种可能：
a.第一次冲过target的时候进行'R'操作，而后反向靠近target。此时曾经走了n + 1步，并且，和target的间隔曾经缩小到了(2^n - 1 -target),能够递归调用helper函数，持续求解子问题。
b.向前走m步，能够通过递归调用helper函数失去最优值，而后采纳策略1.
最终就是min(a, b)，也就是a, b两种可能的最小值。
采纳dp + memo的办法，每当须要计算一个子问题时，先查表看子问题是否曾经被计算过，
如果是，则间接返回；否则，在进行计算，并将后果保留到memo，以便前面计算应用。
public int racecar(int target) { int[] dp = new int[target + 1]; helper(target, dp); return dp[target];}private int helper(int target, int[] dp) { // 如果曾经计算过，间接返回 if (dp[target] > 0) return dp[target]; int n = (int) (Math.log(target) / Math.log(2)) + 1; // 如果刚好是第一种状况target = 2^n - 1，则间接放入后果返回 if (1 << n == target + 1) { dp[target] = n; } else { // 是第二种状况， // 计算a.状况 dp[target] = n + 1 + helper((1 << n) - 1 - target, dp); // 计算b.状况，并取a,b状况下的最小值对dp[target]进行更新 for (int m = 0; m <= n - 1; m++) { int cur = (1 << (n - 1) ) - (1 << m); dp[target] = Math.min(dp[target], n + m + 1 + helper(target - cur, dp)); } } return dp[target];}参考解法：https://www.cnblogs.com/grand...