leetcode 45. 跳跃游戏 II

[xxleyi]

题：
给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：

使用最少的次数跳到终点不能作为「循环不变式」，我们需要转换描述。

想要次数最小，就需要让每一次跳跃的效益最大化。

怎样才能最大化呢？

当我们从 i 跳到 j 再跳到 k 时，在 i 处，我们有多个选择。准确地说，选择范围为 (i, i + nums[i]]。有且仅有这些选择。那我们该怎么选择呢？这些选择又有哪些依赖呢？

有这样具体的切入点之后，具体推演几步，我们意识到选择本身并不难：就是在这个范围里，下一跳最远的那一个。下一跳最远的那个选择，能为我们下一个选择提供一个最大的选择范围。

这么一分析，「循环不变式」有了：针对每一个索引，都有一个当前最远位置和下一个最远位置。

初始化：索引 0 之前的选择范围，题目已经规定好了：0
所以，初始化变量 nextRightMost = rightMost = 0

下面是具体的代码实现：

var jump = function(nums) {
  // initialize two loop invariants related variables
  let nextRightMost = rightMost = 0
  // initialize step to save result
  let step = 0

  for (let i = 0; i < nums.length && rightMost < nums.length - 1; i++) {
    // update nextRightMost to maintain loop invariant
    nextRightMost = Math.max(i + nums[i], nextRightMost)
    // update rightMost to maintain loop invariant
    if (i === rightMost) {
      rightMost = nextRightMost
      step++
    }
  }

  // loop termination: step is our answer
  return step
}