跳跃游戏(三)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    int minSteps = Integer.MAX_VALUE;
    public int minJumpStep (int[] nums) {
        // write code here
        int n = nums.length;
        if(n == 0) return -1;
        if(n == 1) return 0;
        dfs(nums, 0, 0);
        return minSteps == Integer.MAX_VALUE? -1: minSteps;
    }
    
    private void dfs(int[] nums, int cur, int steps) {
        if(cur >= nums.length - 1){
            minSteps = Math.min(minSteps, steps);
            return;
        }
        if(nums[cur] == 0){
            return;
        }
        for(int i = 1; i <= nums[cur]; i++){
            dfs(nums, cur + i, steps + 1);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minJumpStep (int[] nums) {
        // write code here
        int n = nums.length;
        if(n == 0) return -1;
        if(n == 1) return 0;
        int[] dp = new int[n];     // dp[i]表示从i位置到最后一个位置需要的最少步数
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 0;
        for(int cur = n - 2; cur >= 0; cur--){
            for(int i = 1; i <= nums[cur]; i++){
                if(cur + i >= n - 1){
                    // 从cur可以一步到达最后一个位置
                    dp[cur] = 1;
                    break;
                }else{
                    if(dp[cur + i] != Integer.MAX_VALUE){
                        // 在dp[cur+i]能到达最后位置的基础上再加上一步
                        dp[cur] = Math.min(dp[cur], dp[cur + i] + 1);
                    }
                }
            }
        }
        return dp[0] == Integer.MAX_VALUE? -1: dp[0];
    }
}

贪心算法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minJumpStep (int[] nums) {
        // write code here
        int n = nums.length;
        if(n == 0) return -1;
        if(n == 1) return 0;
        int steps = 0, cur = 0, reach = 0;    // 步数，当前位置，可以到达的最远位置
        for(int i = 0; i < n - 1; i++){
            reach = Math.max(reach, i + nums[i]);     // 可以到达的最远位置
            if(i >= reach) return -1;
            if(cur >= n - 1) break;     // 已经可以到达最后一个位置
            if(i == cur){
                steps++;
                cur = reach;
            }
        }
        return steps;
    }
}

public static int minJumpStep(int[] nums) {
        // 大致思路如下：
        // 1.初始化：从第0个台阶开始跳，最远可直接跳到 0 + nums[0] 的位置,
        // 2. 在跳到 nums[0] 之间, 再记录下来 nums[i] + i 的位置，它为最近连续两次跳过的最远位置
        // 3. 如果发现 0 ~ nums[0] 之间，有更优的原则，即连续跳跃两次距离更远，就使用这个更远的距离作为下一次跳跃的开始位置
        //    这是因为 0 ~ nums[0] 之间的任何一个台阶都可以一步到位，所以只需要看两次跳跃的最终距离： nums[i] + i
        // 4. 更新了最大跳跃的下标后，继续循环，循环过程中又继续找最大距离，直到满足最后一个元素.

        // 总结： 第一次初始化的时候选择第一个元素，在遍历过程中调整最优路径，确认最终位置，使得每次更新最终位置都是最优解，遍历结束则是全局最优解
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return 0;

        int maxReach = 0; // 当前能够到达的最远位置
        int steps = 0; // 当前步数,初始化，第一次循环为初始为1
        int currEnd = 0; // 当前步数下，能够到达的最远位置

        for (int i = 0; i < n - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == currEnd) {
                steps++;
                currEnd = maxReach;
            }
            if (currEnd >= n - 1) return steps;
        }

        return currEnd >= n - 1 ? steps : -1;
    }

    public static int minJumpStepDP(int[] nums) {
        if (nums.length == 0)
            return -1;
        int[] dp = new int[nums.length];
        int maxIndex = 0;
        // 从第0个台阶开始尝试
        for (int i = 0; i < nums.length && i <= maxIndex; ++i) {
            // 更新当前 i 的情况下最远能跳到的位置
            maxIndex = Math.max(maxIndex, i + nums[i]);
            // (i+1, i+nums[i]) 之间找最优解
            for (int j = i + 1; j <= i + nums[i] && j < nums.length; ++j) {

                // 初始化
                if (dp[j] == 0)
                    // 当 i > 0 , dp[i] 已经在之前的 dp[j] 中计算好了最优解
                    dp[j] = dp[i] + 1;
                else
                    // 因为 i ~ i+ nums[i] 是一步到位，因此加1
                    dp[j] = Math.min(dp[i] + 1, dp[j]);
                if (j == nums.length - 1)
                    return dp[j];
            }
        }
        return maxIndex >= nums.length - 1 ? dp[nums.length - 1] : -1;//首先判断是否能到达最后，能到达则返回最小步数，不能到达就返回-1.
    }

class Solution {
public:
    int minJumpStep(vector<int>& nums) {
        int n=nums.size();int count=0;
        if(n==0)return -1;if(n==1)return 0;
        vector<int>dp(n,100000);dp[n-1]=0;
        for(int cur=n-2;cur>=0;cur--)
        {
            for(int i=1;i<=nums[cur];i++)
            {
                if(cur+i>=n-1){dp[cur]=1;break;}
                else
                {
                    dp[cur+i]!=100000;
                    dp[cur]=min(dp[cur],dp[cur+i]+1);
                }
            }
        }
        return (dp[0]==100000)?-1:dp[0];
    }
};

class Solution {
public:
    int minJumpStep(vector<int>& nums) {
       int n=nums.size();
        if(n==0)return -1;
        if(n==1)return 0;
        int val=0;int count=0;int cur=0;//cur当前位置， count步数，val能到达的最远距离。
        for(int i=0;i<n-1;i++)
        {
            val=max(val,i+nums[i]);
            if(i>=val)return -1;
            if(cur>=n-1)break;
            if(i==cur)
            {
                count++;cur=val;
            }
        }
        return count;
    }
};