Jump Game

lc 55

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.

Determine if you are able to reach the last index.

greedy 算法，每一点都只在大于最远的时候更新最远

    public boolean canJump(int[] A) {
        int n = A.length;
        int farest = A[0];
        for ( int i = 0 ; i < n; i++ ){
            if ( i <= farest && i + A[i] > farest){
                farest = i + A[i];
            }
        } 
        return farest >= n - 1;
    }

dp 解法1: tle

    public boolean canJump(int[] A) {
        boolean[] can = new boolean[A.length];
        can[0] = true;

        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                    //我的解法写了两个if，代码冗长
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }

        return can[A.length - 1];
    }

lc 45 Jumpgame 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.

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int farest = 0;
        int end = 0; 
        int start = 0; 
        int jumps = 0;
        while ( end  < nums.length - 1){
            jumps++;

            for ( int i = start; i <= end && i < nums.length; i++){
                if (nums[i] + i > farest){
                    farest = nums[i] + i;
                }

            }
            start = end + 1;

            end = farest;
        }

        return jumps;

    }
}