Jump Game II

Question

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

Thoughts

同1, DP都不是最好的algo, greedy更快

Solution

DP

class Solution:
    # @param A, a list of integers
    # @return an integer
    def jump(self, A):
        # write your code here
        length = len(A)
        f = [sys.maxint for i in range(length)]
        f[0] = 1
        for i in range(length):
            if f[i] == sys.maxint:
                continue
            maxLen = A[i]
            for j in range(maxLen + 1):
                if i + j < length:
                    if f[i+j] > f[i] + 1:
                        f[i+j] = f[i] + 1

        return f[length-1]

Greedy

public class Solution {
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return -1;
        }
        int start = 0, end = 0, jumps = 0;
        while (end < A.length - 1) {
            jumps++;
            int farthest = end;
            for (int i = start; i <= end; i++) {
                if (A[i] + i > farthest) {
                    farthest = A[i] + i;
                }
            }
            start = end + 1;
            end = farthest;
        }
        return jumps;
    }
}