题解 | #几步可以从头跳到尾#

时间复杂度：O(n)，其中 n 是数组长度。

空间复杂度：O(1)。

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少需要跳跃几次能跳到末尾
     * @param n int整型 数组A的长度
     * @param A int整型一维数组 数组A
     * @return int整型
     */
    public int Jump (int n, int[] A) {
        // write code here
        int end = 0; // 记录边界
        int maxposition = 0; // 记录最大的位置 也即下次的边界；
        int count = 0; // 记录走过的步数
        for(int i = 0; i < n-1; i++) {
            maxposition = Math.max(maxposition ,i + A[i]); 
            if(i == end){  // 当走到边界的时候，就要更新边界为可达的最远位置
                end = maxposition;
                count++;   // 当走到边界的时候就要更新步数了
            }
        }
        return count;

    }
}

o(n2) o(n)

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;

        // if(len == 1){ return true ; }
        int[] dp = new int[len];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0;i < len;i++){
            int max = i + nums[i];
            for(int j = i+1; j <= max && j < len; j++){
                dp[j] = Math.min(dp[j],dp[i]+1);
            } 
        }
        return dp[len-1];
    }
}