LeetCode Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

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.)

思路分析：这题是Jump Game问题的变形，要求跳到终点需要的最少步数，最简洁的解法是贪心法，我们从前向后扫描数组，用reachable维护当前可以到达的最远的boundary，用farthest维护当前可以跳到的最远位置，如果当前遍历的i已经超过了reachable这个boundary，那么需要更新reachable为当前可以跳到的最远位置farthest。而farthest是Math.max(farthest, i + A[i])，也就是当前扫描过的所有位置中最大的i + A[i]值。这个贪心解法只需要几行就可以AC，要反复体会这类题目的特点。

AC Code:

public class Solution {
    public int jump(int[] A) {
        int step = 0;
        int reachable = 0;
        int farthest = 0;
        for(int i = 0; i < A.length; i++){
            if(i > reachable){
                step++;
                reachable = farthest;
            }
            farthest = Math.max(farthest, i + A[i]);
        }
        return step;
    }
}

LeetCode Jump Game II

原文：http://blog.csdn.net/yangliuy/article/details/42873135