中电科工程建设有限公司网站,济南网站优化排名推广,那个网站可以做空比特币,嘉兴企业自助建站文章目录 题目链接题目描述代码1.动态规划2.贪心 题目链接
55.跳跃游戏
题目描述 代码
1.动态规划
1.1 dp数组的含义 dp[i]#xff1a;从[0,i]的任意一点处出发#xff0c;你最大可以跳跃到的位置。 例如nums[2,3,1,1,4]中: dp[0]2 dp[1]4 dp[2]4 dp[3]4 dp[4]8#xff… 文章目录 题目链接题目描述代码1.动态规划2.贪心 题目链接
55.跳跃游戏
题目描述 代码
1.动态规划
1.1 dp数组的含义 dp[i]从[0,i]的任意一点处出发你最大可以跳跃到的位置。 例如nums[2,3,1,1,4]中: dp[0]2 dp[1]4 dp[2]4 dp[3]4 dp[4]8其实我们没有必要去讨论最后一个下标因为从最后一个下标出发一定可以到最后一个 1.2 dp数组的递推公式 dp[i]max(dp[i−1],nums[i]i) dp[i] 代表的是从[0,i]的任意一点处出发你最大可以跳跃到的位置那么就考虑是否从下标i出发于是dp[i]可以由两个方面推出: 从下标i出发能到达的位置是nums[i]i 不从下标i出发最大能到达的就是dp[i−1] 所以 dp[i]max(dp[i−1],nums[i]i) 由dp[i]的定义可以知道dp[0]nums[0] 1.3 怎么判断是不是可以到达最后一位 从dp[i]的定义我们可以知道dp[i]的大小一定是单调不减的因为nums中的元素都是大于等于0的我们不可能倒着走回来。把我们想象成棋子当遇到什么情况的时候棋子将会原地踏步无法向前进呢其实就是当dp[i]i的时候。试想当棋子来到下标i的时候上帝却告诉它你最多只能到下标i那棋子不就再也不能向前进了吗想通了这个代码就呼之欲出了。
public boolean canJump(int[] nums) {if(nums.length 1){return true;}if(nums[0] 0){return false;}int[] dp new int[nums.length];//从[0,i]的任意一点处出发你最大可以跳跃到的位置dp[0] nums[0];for(int i1;inums.length;i){dp[i] Math.max(nums[i]i,dp[i-1]);if(dp[i] nums.length-1){return true;}if(dp[i] i){return false;}}return true;}2.贪心
每次移动取最大跳跃步数得到最大的覆盖范围每移动一个单位就更新最大覆盖范围。
贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。
i 每次移动只能在 cover 的范围内移动每移动一个元素cover 得到该元素数值新的覆盖范围的补充让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标直接 return true 就可以了。
public boolean canJump(int[] nums) {int cover 0;//覆盖的范围if(nums.length 1){return true;}for(int i0;icover;i){cover Math.max(nums[i]i,cover);if(cover nums.length-1){return true;}}return false;}
