DP&DFS之跳跃游戏合集

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

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

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

C++

//dp 通过全部用例 超时
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n, false);
        dp[0] = true;
        for(int i = 0; i < n; i ++){
            if(!dp[i]) continue;
            for(int j = 1; j <= nums[i] && i + j < n; j++){
                dp[i + j] = true;
            }
        }
        return dp[n - 1];
    }
};

// AC
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int res = 0; // 能达到的下标
        int n = nums.size();
        for(int i = 0; i < n; i ++){
            if(i > res) return false; // 到了达不到的下标,不能再继续下去
            res = max(nums[i] + i, res);
        }
        return res >= n - 1;
    }
};

45. 跳跃游戏 II

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

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

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

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

示例 1:

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

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

C++

• 思路一 : 动态规划

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, INT_MAX); // dp[i] 为到达 i 下标所需的最少跳跃次数
        dp[0] = 0;
        for(int i = 1; i < n; i ++){
            int m = INT_MAX; // 在 j < i中找到 j + nums[j] >= i 且 最小的dp[j]
            for(int j = 0; j < i; j ++){
                if(dp[j] < m && j + nums[j] >= i){
                    m = dp[j];
                    dp[i] = dp[j] + 1;
                } 
            }
        }
        return dp[n - 1];
    }
};
//执行用时：1916 ms, 在所有 C++ 提交中击败了5.01%的用户
//内存消耗：16.8 MB, 在所有 C++ 提交中击败了5.18%的用户

• 思路二 :

1. 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。

2. 如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。

3. 所以，当一次 跳跃 结束时，从下一个格子开始，到现在 能跳到最远的距离，都 是下一次 跳跃 的 起跳点。

   对每一次 跳跃 用 for 循环来模拟。

   跳完一次之后，更新下一次 起跳点 的范围。

   在新的范围内跳，更新 能跳到最远的距离。记录 跳跃 次数，如果跳到了终点，就得到了结果。

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0; // 到达nums[n - 1]的最少步数
        int begin = 0;
        int end = 1; // end 是 该轮最末尾的位置
        while(end < nums.size()){
            int maxReach = 0;
            for(int i = begin; i < end; i ++){ // 如果将end初始化为0的话,第一轮不会展开,出现runtime error
               maxReach = max(nums[i] + i, maxReach);
            }
            begin = end;
            end = maxReach + 1;
            res ++;
        }
        return res;
    }
};
// 执行用时：12 ms, 在所有 C++ 提交中击败了76.15%的用户
// 内存消耗：16 MB, 在所有 C++ 提交中击败了96.52%的用户

1306. 跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 

示例 2：

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3：

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。 

提示：

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

C++

class Solution {
public:
    bool res = false;
    bool canReach(vector<int>& arr, int start) {
        dfs(arr, start);
        return res;
    }

    void dfs(vector<int>& arr, int start){
        int n = arr.size();
        if(start > n - 1 || start < 0 || arr[start] == -1) return;
        
        if(arr[start] == 0){
            res = true;
            return;
        }
        
        int step = arr[start];
        arr[start] = -1; // -1代表已经访问过
        dfs(arr, start + step);
        dfs(arr, start - step);
    }
};

1345. 跳跃游戏 IV

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

• i + 1 需满足：i + 1 < arr.length
• i - 1 需满足：i - 1 >= 0
• j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

提示：

• 1 <= arr.length <= 5 * 104
• -108 <= arr[i] <= 108

C++

// 错误版本, 这样会向右一步一步的走,最后 res 返回的是串长度
class Solution {
public:
    int res = 0;
    int minJumps(vector<int>& arr) {
        dfs(arr, 0, res);
        return res;
    }

    void dfs(vector<int>& arr,int idx, int& res){
        if(idx < 0 || idx > arr.size() - 1) return;
        if(arr[idx] == -1 || idx == arr.size() - 1) return; // 已被访问过
        arr[idx] = -1;
        res ++;
        dfs(arr, idx + 1, res);
        dfs(arr, idx - 1, res);
        for(int j = 0; j < arr.size(); j ++){
            if(j == idx || arr[j] != arr[idx] || arr[j] == -1) continue;
            dfs(arr, j, res);
        }
    }

};