题解 | #青蛙跳跃# 动态规划

遍历数组，每次判断能跳到的最远距离，如果最远距离比之前更远，则步数加1

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pond int整型vector
     * @return int整型
     */
    int minJump(vector<int>& pond) {
        int n = pond.size();
        int step = 0;
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (maxLen < i + pond[i]) {
                maxLen = i + pond[i];
                step++;
            }
            if (maxLen >= n - 1) {
                return step;
            }
        }
        return -1;
    }
};

时间复杂度：O(n)，遍历了一次数组

空间复杂度：O(1)，仅使用了常数空间