45. 跳跃游戏 II

// 给定一个非负整数数组，你最初位于数组的第一个位置。
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
// 假设你总是可以到达数组的最后一个位置。
var jump = function(nums) {
  let n = 0;
  function getStep(arr, step) {
    if (arr.length === 1) {
      n = step;
      return;
    }
    const total = arr.length;
    for (let i = 0; i < arr.length; i++) {
      if (i + arr[i] + 1 >= total) {
        step = getStep(arr.slice(0, i + 1), step + 1);
        break;
      }
    }

    return step;
  }

  getStep(nums, 0);

  return n;
};

console.log(jump([2, 3, 1, 1, 4])); // 2
console.log(jump([2, 3, 0, 1, 4])); // 2
console.log(jump([1, 3, 1, 2, 3, 1, 3, 2, 4])); // 4