jump-game-55.cc

// 使用贪心法的思路，每次跳跃最大的距离，看看是否可以到达终点。
//
// 显然，可能有存在合法路径但每次跳跃最大距离无法到达终点的情况，比如 [3,2,1,0,4]。
//
// 每次跳跃最大距离却无法到达终点的根源在于，贪心算法缺乏“前视”，跳到当前一步能
// 跳到的最远的位置，但这个位置可能只能跳很短的距离。
//
// 为了解决贪心法短视的问题，必须将一步之后的位置上能跳跃的距离也考虑在内。最直
// 接的办法是回溯，尝试所有可能的路径，如果成功则终止流程，否则回溯。
//
// 实际上，考虑在跳跃距离为 N 的位置跳跃几步是无意义的，关键在于在该位置最远可以jump-game-ii
// 条到哪。跳跃的过程实际上是，在跳跃距离为 N 的位置上，可以跳到前面 N 个位置上，
// 即覆盖范围为前面 N 个位置。对于覆盖范围内的每个位置，尝试从该位置往前跳，可能
// 在某个位置跳跃到更远的位置（覆盖范围扩大），不断重复以上过程。
//
// 算法流程：
//   1. 在一个位置上，计算得到该位置能够跳跃到的最远的位置（覆盖范围）
//   2. 然后再从下一个位置出发，计算该位置能够跳跃到的最远距离；以此类推。能否到
//    达终点转化为范围是否可以覆盖到终点。
//
// 流程终止条件：
//   1. 当前位置超出覆盖范围，说明能跳到的最远位置的跳跃距离为 0，不可以再跳跃。
//      比如 [3,2,1,0,4]。
//   2. 覆盖范围覆盖终点，说明可以到达终点。
//
// 为什么这个算法是正确的？
//   这个算法是典型的贪心算法，覆盖范围的扩大实际上是“所有能跳跃的位置都尝试一边，
//   找到这一步能跳到的最远位置”。
//
//   只有当前覆盖范围边界的位置跳跃距离为 0 时才可能才无法到达终点。试想每个
//   位置的跳跃距离都为 1，一步一步跳必定能到达终点。如果覆盖范围内，所有节点都
//   无法跳跃到覆盖范围之外，则无法跳跃到终点；否则，在新的覆盖范围内继续流程。
class Solution {
public:
  bool canJump(vector<int> &nums) {
    int end = 0;
    for (int pos = 0; pos <= end && end < nums.size(); ++pos) {
      if (pos + nums[pos] > end) {
        end = pos + nums[pos];
      }
    }
    return end >= nums.size() - 1;
  }
};