题目链接
LeetCode 55. 跳跃游戏[1]
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1
输入： [2,3,1,1,4] 输出： true 解释： 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2
输入： [3,2,1,0,4] 输出： false 解释： 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
题解
动态规划+正推
动态规划+倒推
贪心+正推
贪心+倒推
代码
动态规划+正推（c++）
classSolution { public: boolcanJump(vector<int>&nums) { intn=nums.size(); vector<int>dp(n, 0); dp[0] =1; for (inti=0; i<n; ++i) { if (!dp[i]) returnfalse; if (i+nums[i] >=n-1) returntrue; for (intj=i+1; j<=i+nums[i]; ++j) { dp[j] =1; } } returnfalse; } };
动态规划+倒推（c++）
classSolution { public: boolcanJump(vector<int>&nums) { intn=nums.size(); vector<int>dp(n, 0); dp[n-1] =1; for (inti=n-2; i>=0; --i) { if (i+nums[i] >=n-1) { dp[i] =1; continue; } for (intj=i+1; j<=i+nums[i]; ++j) { dp[i] |=dp[j]; if (dp[i]) break; } } returndp[0]; } };
贪心+正推（c++）
classSolution { public: boolcanJump(vector<int>&nums) { intn=nums.size(), maxx=0; for (inti=0; i<n; ++i) { if (i>maxx) returnfalse; maxx=max(maxx, i+nums[i]); } returnmaxx>=n-1; } };
贪心+倒推（c++）
classSolution { public: boolcanJump(vector<int>&nums) { intn=nums.size(), minn=n-1; for (inti=n-2; i>=0; --i) { if (i+nums[i] >=minn) minn=i; } return!minn; } };
参考资料
[1]
LeetCode 55. 跳跃游戏: https://leetcode-cn.com/problems/jump-game/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
