- to do

12.1] Jump Game

    bool canJump(vector<int>& nums) {
        int rightMost = 0;
        for (int i=0; i<=rightMost && i<nums.size()-1; ++i) {
            rightMost = max(rightMost, i+nums[i]);
        }
        return rightMost >= nums.size()-1;
    }

stepping from top towards bottom

    bool canJump(vector<int>& nums) {
        int leftMost = nums.size()-1;
        for (int i=nums.size()-2; i>=0; --i) {
            if (i+nums[i] >=leftMost)
                leftMost = i;
        }
        return leftMost==0;
    }

naive

    int jump(vector<int>& nums) {
      if (nums.size()<2) return 0;
      vector<int> minSteps(nums.size(), INT_MAX);
      int i=0; //inspect point
      minSteps[0] = 0;
      for (int j=i+1; j<=i+nums[0] && j<nums.size(); ++j) minSteps[j]=1;
      
      for (; i<nums.size()-1; ++i) {
          if (minSteps[i-1]==INT_MAX) continue;
          for (int j=i+1; j<=i+nums[i] && j<nums.size(); ++j) {
              minSteps[j] = min(minSteps[j], minSteps[i]+1);
          }
      }
      return minSteps[nums.size()-1];
    }

......................................

45. Jump Game II

    int jump(vector<int>& nums) {
        int step=0, start=0, end=0; 
        int n=nums.size();
        while (end<n-1) {
            ++step;
            int maxEnd = end+1;
            for (int i=start; i<=end; ++i) {
                if (i+nums[i] >= n-1) return step;
                maxEnd = max(maxEnd, i+nums[i]);
            }
            start = end+1;
            end = maxEnd;
        }
        return step;
    }