法一跳跃游戏I——贪心算法首先看透题目。看明白题目以后转换一下思路“能否到达终点”改成“最远能跳到哪里”贪心算法只要能到达下标i的位置别管我是怎么到的从i位置起跳能达到的最远距离就是inums[i]然后此时此刻从0到inums[i]的距离都能到达了于是我们更新全局最远fathestMath.max(nums[i]i,fathest)。class Solution { public boolean canJump(int[] nums) { int fathest 0;//记录全局最远 //从下标i起跳 for(int i0;inums.length;i){ if(ifathest){ fathestMath.max(nums[i]i,fathest); }else{ break; } } if(fathestnums.length-1) return true; else return false; } }法二跳跃游戏I——动态规划https://blog.csdn.net/qq_44886213/article/details/124803506法一跳跃游戏II——动态规划我的第一直觉是用动态规划并且直觉告诉我子问题的定义定义dp[i]: 到达i最少跳几次有了子问题的定义就差递推公式了。让我们从头开始推已知dp[0]0假设nums[0]3那dp[1]、dp[2]、dp[3]都可以暂时更新成dp[0]1这个“1”表示1跳。再继续如果nums[1]4那就可以更新dp[1]后面的4个分别是dp[2]、dp[3]、dp[4]、dp[5]但是刚刚dp[2]、dp[3]不是有值了吗这就需要取最小值。但是要注意因为dp初始化的时候都是0用Math.min的时候有坑需要判断一下见代码。class Solution { public int jump(int[] nums) { //简单到不需要写注释 int len nums.length; int[] dp new int[len]; dp[0]0; for(int i0;ilen;i){ for(int j1;jnums[i];j){ if(ijlen) dp[ij]dp[ij]!0 ? Math.min(dp[ij],dp[i]1) : dp[i]1; } } return dp[len-1]; } }法二跳跃游戏II——贪心算法倒着往前走当走到位置i的时候遍历找到前面[0,i-1]里能跳到i的最小的下标也就是一步步往回跳跳的最远的下标。class Solution { public int jump(int[] nums) { int jumpTimes0; int inums.length-1; while(i0){ int maxIndex0; for(int j0;ji-1;j){ if(nums[j]ji){ //从左往右找到第一个能跳到i的 maxIndexj; break; } } //跳到这里 imaxIndex; //跳跃次数1 jumpTimes; } return jumpTimes; } }