Jump Game II leetcode

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

state:f[i] 表示从0到i点最少要跳几部

function： f[i] = f[j] +1 // j< i   j + a[j] >= i 取最小的j

initial：f[0] = 0

return f[a.length-1]
时间O(n^2) 空间O(n)

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    break;
                }
            }
        }
        return count[A.length - 1];
    }
}

如果要输出所有解（从0点jump到i点的路径）

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        int[] pre = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    pre[i] = j;//记录到达i点的前一点j
                    break;
                }
            }
        }
        i = A.length - 1;
        while(i != 0) {
            path.add(i);//把i的值加入结果里
            i = pre[i];//i的值编程i前一点的值
        }
        path.add(0);
        path.reverse;//因为是倒着加的所以要reverse
        return path;
    }
}

greedy解法 在位置i可以跳的最远距离为nums[i] + i , 每次跳完更新max = max(max, num[i] + i)
时间O(n) 空间 O(1)

public class Solution {
    public int jump(int[] nums) {
        int max = 0;
        int lastmax = 0;
        int step = 0;
        for (int i = 0; i <= max && i < nums.length; i++) {
            if (i > lastmax) {//在第0位置 如果i大于0的话就至少走一步, 更新lastmax为0位置走一步最远能到的位置
                lastmax = max;
                step++;
            }
            max = Math.max(max, nums[i] + i);
        }
        if (max < nums.length - 1) {
            return 0;
        }
        return step;
    }
}