45. 跳跃游戏 II

解法1

动态规划

大致思路，同跳跃游戏 1.jie

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] jumpCntArr = new int[n];
        for (int i = n - 2; i > -1; i--) {
            int right = Math.min(n, i + nums[i] + 1);
            int tmpMin = 100000;
            for (int j = i + 1; j < right; j++) {
                if (jumpCntArr[j] < tmpMin) {
                    tmpMin = jumpCntArr[j];
                }
            }
            jumpCntArr[i] = tmpMin + 1;
        }
        return jumpCntArr[0];
    }
}

解法2

题目保证可达。

那么，每一次从前往后选最左的坐标，一定是最短距离

class Solution {
    public int jump(int[] nums) {
        int now = nums.length - 1, ans = 0;
        while (now > 0) {
            for (int i = 0; i < now; i++) {
                if (i + nums[i] >= now) {
                    now = i;
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}

解法3

维持一个最大的可达右边界。每次到达最大可达右边界，步数加1

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int end = 0;
        int steps = 0;
        int maxPos = 0;
        for (int i = 0; i < n - 1; i++) {
            maxPos = Math.max(maxPos, i + nums[i]);
            if (end == i) {
                end = maxPos;
                steps++;
            }
        }
        return steps;
    }
}

解法4

递归

class Solution {
    private HashMap<Integer, Integer> cache = new HashMap<>();

    public int jump(int[] nums) {
        return justJump(nums, 0);
    }

    public int justJump(int[] nums, int start) {
        if (start >= nums.length - 1) {
            return 0;
        }
        if (nums[start] <= 0) {
            return 100000;
        }
        if (cache.containsKey(start)) {
            return cache.get(start);
        }
        int minStep = 100000;
        for (int i = 1; i <= nums[start]; i++) {
            minStep = Math.min(minStep, justJump(nums, start + i));
        }
        cache.put(start, minStep + 1);
        return minStep + 1;
    }
}