**LeetCode 45. Jump Game II 思维题

本文主要是介绍**LeetCode 45. Jump Game II 思维题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/jump-game-ii/

这道题很不错，我的一种代码感觉本质上跟Ans一样，但是TLE....因为我的写法还是会有重复

思路一：DP

倒过来看，dp[lastIdx-1]=0,

dp[i] = min(1+dp[i+k])   k=1,2....nums[i].

果断TLE

const int MAX = 1147483647;
const int SIZE = 100000+1;
class Solution {
public:int jump(vector<int>& nums) {for(int i=nums.size()-1;i>=0;i--) {dp[i] = MAX;if(nums[i] >= nums.size()-1) {dp[i] = (i==nums.size()-1)?0:1;continue;}for(int j=1;j<=nums[i] && i+j<nums.size(); j++) {dp[i] = min(dp[i], 1+dp[i+j]);}}return dp[0];}
private:int dp[SIZE];
};

思路二：贪心

还是TLE了，但是其实跟正确思路我觉得是一样的。

有点猜的想法：假设从i能到达5,6,7三个位置，那就跳到k，其中k满足nums[k]是最大的。但是仍然有重复判断

class Solution {
public:int jump(vector<int>& nums) {int left=0,mx,pos,ret =0;while(left < nums.size()-1) {mx = 0;pos = left;for(int i=1;i<=nums[left] && left+i<nums.size();i++) {if( nums[i+left] >= mx ) {pos = i;mx = nums[i+left];}if(left+i >=nums.size()-1) {pos = i;break;}}left += pos;ret++;}return ret;}
};

思路三，贪心

class Solution {
public:int jump(vector<int>& nums) {int curdis = 0;int lastpos = 0;int ret = 0;for(int i=0;i<nums.size();i++) {if(i>lastpos) {ret ++;lastpos = curdis;}curdis = max(curdis, i+nums[i]);}return ret;}
};

上面的代码没有考虑如果不能到达的情况，更健壮的代码是：

class Solution {
public:int jump(vector<int>& nums) {int curdis = 0;int lastpos = 0;int ret = 0;for(int i=0;i<nums.size();i++) {if(i>lastpos) {ret ++;lastpos = curdis;if(lastpos >= nums.size()-1)return ret;}if(i+nums[i] >= curdis && lastpos+nums[lastpos]>=i)curdis = i+nums[i];}if(lastpos < nums.size()-1)return -1;return ret;}
};

这篇关于**LeetCode 45. Jump Game II 思维题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---