关于算法:LC818-Race-Car

https://leetcode.com/problems…

Hard
Google, Amazon

第一种解法应用 BFS

// bfs
public 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] 有两种可能：

1. target 刚好是由 ”AAA…A” 一共 n 步达到，也就是一路减速，那么这种走法就是最优抉择。
2. 如果不是上述情况，就有多种可能：
   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…