牛客网. 跳跃游戏-II

题目概述

解题思路

我开始想到的做法是贪心。首先维护两个指针i和cur，i用于顺序遍历，cur用来指向上一次可以跳到的最远的位置。维护一个一维数组，用来记录跳到每个位置需要的最短步数。然后考虑当前能跳到的最远距离是否超过了cur，如果超过，就把cur+1~i+A[i]这些位置的值都置为dp[i]+1；否则就不操作。我们可以保证dp[i]的值就是跳到每个位置所需最短步数，因为当dp[i]被赋值的时候，这个值被第一次访问，之后如果还有别的方法能访问到该值，其步数也必定不少于第一次访问。这个做法的时空复杂度均为O(n)。

考虑这道题的特殊性：跳跃的步数是从1~A[i]连续的，而不是只有A[i]这一个值，因此我们其实只需要维护一个变量，记录当前所能跳到的最远位置即可。如果当前可以跳到超过数组长度的位置，那么必定能跳到数组的末端位置。这样空间复杂度就变为O(1)啦。

方法性能

示例代码

时空复杂度O(n)版：

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @return int整型
     */
    int jump(int* A, int n) 
    {
        // write code here
        int *dp = new int[n];
        memset(dp, 0, sizeof(int) * n);
        
        int cur = 0;
        for(int i = 0; i < n;++i)
        {
            if(i + A[i] > cur)
            {
                for(int j = min(i + A[i], n-1); j > cur;--j)
                    dp[j] = dp[i] + 1;
                cur = i + A[i];
                if(cur >= n)
                    break;
            }
        }
        
        return dp[n-1];
    }
};