[DP]45. Jump Game II

前篇 55. Jump Game
45. Jump Game II

感谢Jason_Yuan大神优秀的解析：链接

解题思路

方法一：贪心(Greedy)
维护一个farthest变量，每次在遍历start到end之间的元素，尝试更新farthest变量
start = end + 1
end = farthest
比较end是否大于数组长度，大于返回结果，否则steps += 1

Java[14.04 %]:

class Solution {
    public int jump(int[] nums) {
        if(nums.length <=1) return 0;
        int step = 0;
        int farthest = 0;
        int end =0;
        int start =0;
            //Because "you can always reach the last index", don't need to check the last element, end<length -1.
        while(end < nums.length-1){
            farthest = end;
            for(int i = start; i<= end; i++){
                if(farthest < i + nums[i]){
                    farthest = i+nums[i];
                }
              }
            step++;
            start = end + 1;
            end = farthest;
        }

        return step;
    }
}

参考大神的改进[90.82 %]：

class Solution {
    public int jump(int[] nums) {
        if(nums.length <=1) return 0;
        int step = 0;
        int farthest = 0;
        int end =0;
        //Because "you can always reach the last index", don't need to check the last element, end<length -1.

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

        return step;
    }
}

Python:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return -1
        
        start, end, steps = 0, 0, 0
        while end < len(nums) - 1:
            steps += 1
            farthest = end
            for i in range(start, end + 1):
                if nums[i] + i > farthest:
                    farthest = nums[i] + i
            start = end + 1
            end = farthest
        
        return steps
 

方法二：动态规划(领会思路，OJ会超时)
开辟一个steps数组长度与input数组相同，初始值为maxint
steps[0] = 0
steps[i]等于遍历steps[0] ~ steps[i-1]，如果存在nums[x] + x > i，则更新steps[i] = steps[x] + 1