谷歌服务加速 wordpress,南宁网站优化公司电话,建设网站培训的ppt,营口 微网站建设45. 跳跃游戏 II
解题思路 int[] memo;#xff1a;定义一个数组memo#xff0c;用来作为备忘录#xff0c;存储从每个索引位置跳到数组末尾所需的最小跳跃次数。 Arrays.fill(memo, n);#xff1a;在开始计算之前#xff0c;先将memo数组的所有元素初始化为n。这里的n是…45. 跳跃游戏 II
解题思路 int[] memo;定义一个数组memo用来作为备忘录存储从每个索引位置跳到数组末尾所需的最小跳跃次数。 Arrays.fill(memo, n);在开始计算之前先将memo数组的所有元素初始化为n。这里的n是输入数组nums的长度初始化为n是因为从任何位置到最后位置的跳跃次数不可能大于n-1。 dp(nums, 0);调用dp函数从索引0开始计算到达最后位置的最少跳跃次数。 dp函数这个函数是解题的核心它递归地计算从当前位置p到最后位置所需的最少跳跃次数。 如果p已经大于或等于n-1即已经到达或超过了数组的最后位置则不需要再跳跃返回0。 如果memo[p]不等于n说明这个位置的最少跳跃次数已经被计算过了直接返回memo[p]的值。 对于当前位置p尝试所有可能的跳跃步数从1到nums[p]并递归地调用dp函数计算每一种选择后的最少跳跃次数。选择所有可能中的最小值加1当前这一跳作为memo[p]的值。
class Solution {// ListInteger memo new ArrayList();// 作为备忘录记忆int[] memo;// 记录每一个索引位置跳跃最后一个位置要多少次public int jump(int[] nums) {// 动态规划int n nums.length;// 初始化备忘录memo new int[n];Arrays.fill(memo,n);// 所有元素全部初始化为n 因为从0 到n - 1 不会超过n - 1return dp(nums,0);}int dp(int[] nums,int p){// 返回值 从索引p跳到最后一个位置所需要的最少次数int n nums.length;if(p n - 1){return 0;}// 判断子问题是不是计算过if(memo[p] ! n){return memo[p];}int steps nums[p];// 然后从当前位置可以选择跳跃 1 2 3 4 5 ... steps步for(int i 1; i steps;i){// 跳跃i步 到下一个位置 然后计算结果int subProbelm dp(nums, p i);// 取其中最小的作为最终结果memo[p] Math.min(memo[p],subProbelm 1);}return memo[p];}
}
