纯dp会超时
/* * @lc app=leetcode id=45 lang=cpp * * [45] Jump Game II */ // @lc code=start class Solution { public: int jump(vector<int>& nums) { int N = nums.size(); vector<int> dp(N,-1); for(int i=0;i<N;i++){ dp[i] = i; } for(int i=0;i<N;i++){ for(int j=i+1;j<min(N,i+1+nums[i]);j++){ dp[j] = min(dp[j],dp[i]+1); } } return dp[N-1]; } }; // @lc code=end像这种只往前走，求最短路径的，可以考虑游标+BFS：
/* * @lc app=leetcode id=45 lang=cpp * * [45] Jump Game II */ // @lc code=start class Solution { public: int jump(vector<int>& nums) { int N = nums.size(); if(N <= 1) return 0; queue<pair<int,int>> q; q.push(make_pair(0,0)); // loc,level int cur = 1; // cursor while(!q.empty()){ int loc = q.front().first; int level = q.front().second; for(int i=cur;i<min(N,loc+1+nums[loc]);i++){ q.push(make_pair(i,level+1)); if(i == N-1){ return level+1; } } cur = min(N,loc+1+nums[loc]); q.pop(); } return -1; } }; // @lc code=end /* * @lc app=leetcode id=55 lang=cpp * * [55] Jump Game */ // @lc code=start class Solution { public: bool canJump(vector<int>& nums) { int N = nums.size(); int cur = 0; int ans = 0; queue<int> q; q.push(0); while(!q.empty()){ int now = q.front(); for(int i=cur+1;i<=min(N-1,now+nums[now]);i++){ q.push(i); } cur = max(cur,now + nums[now]); q.pop(); } if(cur >= N-1) return true; return false; } }; // @lc code=end