动态规划:文章来源:https://www.toymoban.com/news/detail-830837.html
1.声明一个dp数组来表示到下标i时要跳转的最小次数,同时要个每个dp数组的值赋值为最大。之后初始化dp【0】=0,用for循环来进行遍历下标i和遍历下标i之前的值,判断条件为如果i之前的某个下标跳转的距离>=i时要根新dp【i】的值 ,递推公式为dp【i】=math,min(dp[i],dp[j]+1)。表示在这个跳转范围里dp【i】的值为dp【j】加一。文章来源地址https://www.toymoban.com/news/detail-830837.html
class Solution {
public int jump(int[] nums) {
//表示的是跳转到下标为i时要跳转的最小次数
int [] dp=new int [nums.length];
//给每个dp数组的值赋值为数组的最大长度
for(int i=1;i<nums.length;i++){
dp[i]=nums.length;
}
//初始化dp【0】时跳转次数为0
dp[0]=0;
//来遍历下标i
for(int i=1;i<nums.length;i++){
//遍历下标i之前的值
for(int j=0;j<i;j++){
//判断跳转的最远距离只要在这个距离中dp【i】的值就为dp【j】加一
if(j+nums[j]>=i){
dp[i]=Math.min(dp[i],dp[j]+1);
}
}
}
return dp[nums.length-1];
}
}
到了这里,关于力扣:45. 跳跃游戏 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!