Neovim-如何使用编辑器的神

跳跃游戏 II

https://leetcode.cn/problems/jump-game-ii/

假设$f(i)$表示从下标为0的地方跳到下标为$i$的地方所需要的最小步数.

首先, $f(0) = 0$.

假设$j$是最小的, 能够一步跳到下标为$i$的位置, 那么$f(i) = f(j) + 1$.

因此, 每次找到最小的, 能够一步跳到下标为$i$的位置$j$, 更新状态即可.

class Solution {
public:
    int jump(vector<int>& nums) {

       int n = nums.size();
       vector<int> f(n);

       for (int i = 1, j = 0; i < n; i ++) {
         /* 找到最小的, 能够一步跳到下标为i的位置j */
           while (j + nums[j] < i) j ++;
           f[i] = f[j] + 1;
       }

       return f[n - 1];
    }
};

跳跃游戏

https://leetcode.cn/problems/jump-game/

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for (int i = 0, j = 0; i < nums.size(); i ++) {
            if (j < i) return false;
            /* 维护一个j, 记录j前面的所有元素能够跳到的最大距离 */
            j = max(j, i + nums[i]);
        }
        return true;
    }
};