题解 | #跳跃游戏(一)#

//此解法是练习动态规划而写，因为时间复杂度为O(n的平方)，所以会运行超时
class Solution {
    public boolean canJump(int[] nums) {
        //传入有n个整数的数组
        //判断数组的合法性
        if(nums == null || nums.length == 0){
            return false;
        }
        //数组长度
        int n = nums.length;
        //定义一个Boolean类型的数组
        //f[j]表示能不能跳到石头j
        boolean[] f = new boolean[n];
        //初始化条件f[0]处是刚开始处于的位置，肯定能到达，所以为true
        f[0] = true;
        //外层循环是计算从1位置到数组的最大下标位置是否能跳到
        //计算f[1]...f[n-1]
        for(int j = 1;j < n;j++){
            f[j] = false;//如果能跳到就置为true
            //里层循环表示枚举上一个跳到的石头
            //最后一步：从i跳过来
            for(int i = 0;i < j;i++){
                //要满足两个条件
                //1.首先得能够跳到i
                //2.其次i+nums[i] >= j也就是最后一步的距离不能超过nums[i]
                //j-i<=nums[i]
                if(f[i] && i + nums[i] >= j){
                    f[j] = true;
                    break;
                }
            }
        }
        //返回最后一步
        return f[n-1];
    }
}