55. 跳跃游戏

题目链接

解题思路

• 方法一：(注：这种方法过不了，提供一种思路，如果只想过题，可直接跳转到方法二)自顶向下的动态规划，先写暴力递归过程，然后再直接加缓存表即可。

  • bool process(nums, index, next)

    • nums：固定参数
    • index：当前来到的下标
    • next：能够走到的最远的下标

  • 来到index，怎么考虑？举个例子，假设index为3，next是5，代表我现在在3号下标，我最远能够走到5，那么我要怎么走？

    • 我可以走到4，然后后续接着走int res = process(nums, 4, 4 + nums[4])
    • 我也可以走到5，然后后续接着走int res = process(nums, 5, 5 + nums[5])
    • 很明显，就是一个for循环。注意到，只要一个返回了true，那么就不用接着往下走了，

  • 代码一

    class Solution {
    public:
    
        // index是当前来到的位置，next是能够到达的位置
        // 数据情况   index <= next
        bool process(const vector<int> &nums, int index, int next) {
            if (next >= nums.size() - 1) {    // 注意题目返回条件，到达最后一个下标即可
                return true;
            }
            // 下一步我走哪？
            for (int i = index + 1; i <= next; ++i) {
                int res = process(nums, i, i + nums[i]);
                if (res) {     // 只要走成功了，就不用再试了
                    return true;
                }
            }
            // 上面所有路都走不了
            return false;
        }
        bool canJump(vector<int>& nums) {
            return process(nums, 0, nums[0]);
        }
    };
    

    

    • 下面直接加缓存，缓存怎么理解？我们可以看见主函数调用了process(nums, 0, nums[0])，也就是说，这个结果和传入的参数有关(这不是废话吗？)，具体到递归函数里面，nums是不会变的，可变的就是两个参数，所以，我们可以用表记下来，比如，当index = 2， next = 4时，结果是什么
      • 为什么要记下来？因为有重复的结果，
        • 例如[2, 2, 1, ....]，当前来到index为0，next为2，
          • 你可以选择走到1，那么就调用process(nums, 1, 3)，然后接下来怎么走？你可以选择走到2，那么就调用process(nums, 2, 3)
          • 你也可以选择走到2，那么就调用process(nums, 2, 3)，可以看到，和上面重复了。
      • 直接加缓存这种，其实就是「动态规划」，只不过是自顶向下的动态规划。

  • 代码二

    class Solution {
    public:
    
        // index是当前来到的位置，next是能够到达的位置
        // 数据情况   index <= next
        bool process(const vector<int> &nums, int index, int next, vector<vector<int>> &dp) {
            if (next >= nums.size() - 1) {    // 注意题目返回条件，到达最后一个下标即可
                return true;
            }
            if (dp[index][next] != -1) {     // 因为我初始化是-1，不等于-1说明算过了
                return dp[index][next];
            }
            // 下一步我走哪？
            for (int i = index + 1; i <= next; ++i) {
                int res = process(nums, i, i + nums[i], dp);
                if (res) {     // 只要走成功了，就不用再试了
                    dp[index][next] = 1;    // 1表示true
                    return true;
                }
            }
            // 上面所有路都走不了
            dp[index][next] = 0;
            return false;
        }
        bool canJump(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> dp(n, vector<int>(n, -1));
            return process(nums, 0, nums[0], dp);
        }
    };
    

    • 

      • 很可惜，爆内存了(那你说这么干嘛？这种暴力递归的能力很重要，很多动态规划就是这样出来的)，那么接下来看第二种方法。

• 方法二：其实我们并不需要把所有的「路」都走一遍，我们只需要用一个变量记住，我们「最远」能跑到哪里就行了

  • 例如nums = [2,3,1,1,4]，我们初始在0号位置，我们最远能跑到哪里去？next = 2 + 0，然后我们来到1号位置，我们能来吗？能来，因为next是2，然后我们最远能跑到哪里去？原来是2，现在是3 + 1，所以要更新next，直接看代码，更加清晰。

  • 代码

    class Solution {
    public:
        bool canJump(vector<int>& nums) {
            int next = nums[0];
            int n = nums.size();
            for (int i = 1; i < n; ++i) {
                if (i > next) {    // 不好意思   走不到i  直接返回false
                    return false;
                }
                next = max(next, i + nums[i]);
                // if (next >= n - 1) {    // 提前结束   加了反而变慢了。。数据问题
                //     return true;
                // }
            }
            return true;
        }
    };