题解 | #跳跃游戏#

跳跃游戏

https://www.nowcoder.com/practice/b7d9d79453bf43bf9594e91d24260605

分析：

一、递归

终止返回条件：k>=nums.size()-1;

当前层任务：遍历该位置能到达的所有位置。

路径分支任务：统计该路径的跳跃次数。

class Solution {
public:
  int recursion(vector<int>& nums,int k)
{
    if (k >= nums.size() - 1) return 0;

    int tmp = 0;
    for(int i=1;i<=nums[k];i++) {
      tmp = tmp == 0 ? recursion(nums, k + i) + 1 : min(tmp, recursion(nums, k + i) + 1);
    }
    return tmp;
  }
  int numJump(vector<int>& nums) {
    return recursion(nums, 0);
  }
};

优化：记忆化搜索

class Solution {
public:
  int help[100007];
  int recursion(vector<int>& nums,int k)
{
    if (k >= nums.size() - 1) return 0;
    if (help[k] != 0x3f3f3f3f) return help[k];

    int tmp = 0;
    for(int i=1;i<=nums[k];i++) {
      tmp = tmp == 0 ? recursion(nums, k + i) + 1 : min(tmp, recursion(nums, k + i) + 1);
    }
    help[k] = tmp;
    return tmp;
  }
  int numJump(vector<int>& nums) {
    memset(help, 0x3f, sizeof help);
    return recursion(nums, 0);
  }
};

二、动态规划

f[i]:表示到达末尾的最小跳跃次数。

f[i]=min{ f[i位置能到达的位置] }+1；

f[末尾]=0;

class Solution {
public:
  int numJump(vector<int>& nums) {
    vector<int> f(nums.size(), 0x3f3f3f3f);
    f[nums.size() - 1] = 0;
    for(int i=nums.size()-2;i>=0;i--) {
      if (i + nums[i] >= nums.size() - 1) f[i] = f[nums.size()-1] + 1;
      for(int j=1;j<=nums[i]&&i+j<nums.size();j++) {
        f[i] =min(f[i], f[i + j] + 1);
      }
    }
    return f[0];
  }
};

时间复杂度：O(N^2)

空间复杂度：O(N)

三、每次往最远距离移动

使用变量记录当前最远距离，以及当前距离达不到时之前遍历的位置跳一步所能达到的最远距离。记录每次跳一步的次数即可。

jump:表示当前跳了多少步。

cur：表示当前所能达到的最远距离。

next:表示再多跳一步所能达到的最远距离。

遍历i，

如果cur>=i说明可以到达i位置，使用next记录i位置所能达到的最远距离。

否则则说明无法达到i位置，将cur改为当前最远距离next，jump++;

class Solution {
public:
  int numJump(vector<int>& nums) {
    int jump = 0;
    int next = 0;
    int cur = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (cur < i) {
        cur = next;
        jump++;
      }
      next = max(next, i + nums[i]);
    }
    return jump;
  }
};

时间复杂度：O(N)

空间复杂度：O(1)