core problems►leetcode

LeetCode 45. Jump Game II

Problem

LeetCode 45. Jump Game II

1. 题目简述

给出一个整形非负数组，初始在index为0的位置，每个位置上的数代表其所能跳跃的最大长度（不是只能跳跃该长度），保证一定能够跳到末尾节点，求从0节点跳到末尾节点的最少跳跃次数。例如：

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

2. 算法思路

Brute Force

首先，暴力求解法直接pass，我们需要遍历所有的步长，我们假设F(x)为从index为x的节点到末尾节点的最短jump数。暴力求解法伪代码：

F(x):
    if x >= n - 1
        return 0;
    maxStep = nums[x];
    for i from 1 to maxStep:
        memo[x] = min(memo[x], F(x + i) + 1)
    return memo[x]

Dynamic Programming

这里我们也可以用DP来减少重复计算，对于每个节点到末尾节点最少跳跃次数设为函数F(x)，用memo数组来进行记录并更新。下面是top-down和bottom-up的两种算法。

DP1 top-down：

记录一个memo数组，长度为n，每个元素初始化为n（因为数组长度为n，最多跳跃次数也不过是n-1），计算F(0),对于每个0节点能到达的步长，进行比较，记录，找出最小的那个+1即为0节的最少跳跃数。

DP2 bottom-up:
记录一个memo数组，bottom-up算法就是要从base case开始进行计算，一直到目标target，本题中，base case是memo[n-1]=1，所以我们要从n-2开始往回遍历，判断n-2节点能否到达n-1节点，如果能，则memo[n-2]=1，不能则为0，一直遍历到memo[0]，返回memo[0]。

两种DP算法时间复杂度均为O(n^2)，空间复杂度为O(n)。

Greedy

本题是要找最少的跳跃步数，也就是说我们希望每一步都尽可能要跳得远，步子迈得大。举个例子：
[2,3,1,1,4]，我们在0节点时，最大步长为2，因此最元能到达1和2两个节点，其最大步长分别为3和1，如果我们想走得远，我们当然希望能够第一次走到1节点，它的最大步长为3，可以到达4节点。

因此我们可以看出，对于初始节点0，它能够到达的最远为farthest为end，然后我们从0到end遍历找出其中x节点能跳到最远距离新的farthest，本次跳跃就跳到x节点，jump++，新的end为farthest，以此类推。直到最后，返回jump值。

3. 解法

  1. 暴力解法（Pass，上面有伪代码）
  2. DP top-down

class Solution{
    public int jump(int[] nums) {
        int n = nums.length;
        int[] memo = new int[nums.length];
        Arrays.fill(memo, n);
        return minimumJump(nums, 0, memo);
    }

    private int minimumJump(int[] nums, int x, int[] memo) {
        int n = nums.length;
        if (x >= n - 1) {
            return 0;
        }
        if (memo[x] < n) {
            return memo[x];
        }

        int maxStep = nums[x];
        for (int i = 1; i <= maxStep; i++) {
            memo[x] = Math.min(memo[x], minimumJump(nums, x + i, memo) + 1);
        }

        return memo[x];
    }
}
  1. DP bottom-up
class Solution{
    public int jump(int[] nums) {
        int n = nums.length;
        int[] memo = new int[nums.length];
        Arrays.fill(memo, n);
        memo[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            int maxStep = nums[i];
            for (int j = 1; j <= maxStep; j++) {
                if (i + j > n - 1) {
                    break;
                }
                memo[i] = Math.min(memo[i], memo[i + j] + 1);
            }
        }

        return memo[0];
    }
}
  1. Greedy
class Solution{
    public int jump(int[] nums) {
        int currEnd = 0, farthest = 0, jump = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currEnd) {
                currEnd = farthest;
                jump++;
            }
        }

        return jump;
    }
}