Leetcode 1345. Jump Game IV

[Woodyiiiiiii]

这道题我还想着用DP，重点在如何解决i-1这个问题，难道要逆序DP吗？

无法推导了，说明DP不可行了。那就尝试另一种方法。

那么只能继续看题目条件了，重点是如何解决这套jump规则问题，而且还是在最少步数下跳到最后一个位置。

可以继续推导，可以发现，把数组每个元素看成一个点，跳跃规则就是边，那么这就是个图问题，所以可以从BFS/DFS来考虑，暴力穷举所有跳跃可能位置。

这种数组内用BFS/DFS的题也很多的，比如：

• 1345. Jump Game IV
• 1306. Jump Game III
• 695. Max Area of Island

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            map.computeIfAbsent(arr[i], x -> new ArrayList<>()).add(i);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            while (sz-- > 0) {
                int u = queue.poll();
                if (u == n - 1) {
                    return step;
                }
                if (u - 1 >= 0 && !visited[u - 1]) {
                    queue.offer(u - 1);
                    visited[u - 1] = true;
                }
                if (u + 1 < n && !visited[u + 1]) {
                    queue.offer(u + 1);
                    visited[u + 1] = true;
                }
                for (int v : map.get(arr[u])) {
                    if (!visited[v]) {
                        queue.offer(v);
                        visited[v] = true;
                    }
                }
                map.get(arr[u]).clear();
            }
            ++step;
        }
        return -1;
    }
}