h5网站开发流程图,30岁做网站编辑,网站开发支付功能怎么做,wordpress搭建电子商务一)跳跃游戏: 55. 跳跃游戏 - 力扣#xff08;LeetCode#xff09; 一)定义一个状态表示: dp[i]表示以i未知元素为起点#xff0c;是否能够到达最后一个位置 二)根据状态表示推到状态转移方程:根据最近的一步来进行划分问题 我们可以从当前i位置向后走j步#xff0c;看看从… 一)跳跃游戏: 55. 跳跃游戏 - 力扣LeetCode 一)定义一个状态表示: dp[i]表示以i未知元素为起点是否能够到达最后一个位置 二)根据状态表示推到状态转移方程:根据最近的一步来进行划分问题 我们可以从当前i位置向后走j步看看从ij的位置是否能够到达最后一个位置那么就说明从i位置可以到达ij位置从ij位置可以到达最后一个位置那么就是说明从i位置是可以到达最后一个位置的 class Solution {public boolean canJump(int[] nums) {//dp[i]表示以i位置为起点,是否能够到达最后一个位置boolean[] dpnew boolean[nums.length];dp[nums.length-1]true;for(int inums.length-2;i0;i--){for(int j0;jnums[i];j){if(dp[ij]true){
//只要能够保证后面有一个值可以跳跃到array.length-1的位置,dp[i]的值就是truedp[i]true;break;}}}return dp[0];}
} 三)初始化填表顺序返回值 填表顺序:从左向右初始化为dp[array.length-1]true返回值是dp[0] 二)跳越游戏(2) 45. 跳跃游戏 II - 力扣LeetCode class Solution {public int jump(int[] nums) {
//dp[i]表示以i位置为起点,是否能够到达最后一个位置的下标boolean[] dpnew boolean[nums.length];int[] gnew int[nums.length];
//g[i]表示以i位置元素为开始,到达元素末尾的最小次数for(int i0;ig.length;i){g[i]Integer.MAX_VALUE;}dp[nums.length-1]true;g[nums.length-1]0;for(int inums.length-2;i0;i--){//分为两种情况,从i位置有直接能力开始直接跳转到最后一个位置if(nums[i]nums.length-1){g[i]1;dp[i]true;continue;} //再分为一种情况,从i位置先跳转到j位置,再求从j位置到达结尾的最小次数for(int j1;jnums[i];j){if(ijnums.length-1dp[ij]true){dp[i]true;g[i]Math.min(g[i],g[ij]1);}}}System.out.println(Arrays.toString(g));return g[0];
}
}
