Jump Game II

Problem: Jump Game II

To solve this problem, we need to be greedy at each jump. How to do that? Take [2, 3, 1, 1, 4] as an example. When we stand at the first position, we can see that we can jump to position 2 with value 3 and position 3 with value 1. We calculate we can go as far as 5 through position 2 and 4 through position 3. By this, we can judge that jump to position 2 is a better solution because we can go further.

Code in Python:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1: return 0
        steps, pos, target = 0, 0, len(nums)-1
        while True:
            if pos + nums[pos] >= target:
                return steps + 1
            max, next = 0, pos
            for x in xrange(pos+1, pos+nums[pos]+1):
                if x-pos+nums[x] > max:
                    max, next = x-pos+nums[x], x
            pos, steps = next, steps+1

Code in Java:

public class Solution {
    public int jump(int[] nums) {
        int pos = 0, steps = 0, n = nums.length;
        while (pos < n-1) {
            int next = 0, max = 0;
            for (int i = 1; i <= nums[pos]; i++) {
                if (pos + i >= n - 1) {
                    return steps + 1;
                }
                if (pos + i >= n || i + nums[pos+i] > max) {
                    max = i + nums[pos+i];
                    next = pos+i;
                }
            }
            steps ++;
            pos = next;
        }
        return steps;
    }
}