55. Jump Game 是否能跳到最后

数组中每个元素表示从当前位置能够跳的步数，判断是否能跳到最后。

思考：本题在solution中有4中解法，（方法1）dfs，实际运行会超时，因为会有数组很长的case. (方法2)dfs优化版，不过也会超时。（方法3）动态规划。（方法4）贪心算法。

解法：

（方法1）dfs, 虽然会超时，不过这种解法需要掌握。

bool canJumpFromPos1(int pos, vector<int>& nums) { if (pos + 1 == nums.size()) { return true; } int further_jump = min(pos + nums[pos], (int)nums.size() - 1); for (int i = pos + 1; i <= further_jump; ++i) { if (canJumpFromPos1(i, nums)) { return true; } } return false; } bool canJump1(vector<int>& nums) { return canJumpFromPos1(0, nums); }

（方法2）dfs 剪枝优化

enum Index { GOOD, BAD, UNKNOW }; // Time Limit Exceeded bool canJumpFromPos2(int pos, vector<int>& nums) { if (pos + 1 == nums.size()) { return true; } if (sign[pos] != UNKNOW) { return sign[pos] == GOOD; } int further_jump = min(pos + nums[pos], (int)nums.size() - 1); for (int i = pos + 1; i <= further_jump; ++i) { if (canJumpFromPos2(i, nums)) { sign[pos] = GOOD; return true; } } sign[pos] = BAD; return false; } bool canJump2(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) { sign.push_back(UNKNOW); } sign[nums.size() - 1] = GOOD; return canJumpFromPos2(0, nums); }

（方法3）dp

// Solution 3 556 ms 10.4 MB bool canJump3(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) { sign.push_back(UNKNOW); } sign[nums.size() - 1] = GOOD; for (int pos = nums.size() - 2; pos >= 0; --pos) { int further_jump = min(pos + nums[pos], (int)nums.size() - 1); // [pos + 1, further_jump] 是pos能够跳过的区间，这里只要有能够到达的位置，那么pos也就能到达 // 所以下面会遍历这个区间，当有GOOD时，pos位置也能够置为GOOD for (int j = pos + 1; j <= further_jump; ++j) { if (sign[j] == GOOD) { sign[pos] = GOOD; } } } return sign[0] == GOOD; }

(方法4) 贪心算法

// Solution 4 Greedy bool canJump(vector<int>& nums) { int last_pos = nums.size() - 1; for (int i = nums.size() - 1; i >= 0; --i) { if (i + nums[i] >= last_pos) { last_pos = i; } } return last_pos == 0; }