题目

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

分析

O(n^2)的算法很容易想到，就是从后往前扫描，计算并记录每个位置到达末尾需要的步数。计算每个位置的步数时，只需要从该位置开始往后扫描到其能达到的最大步长，取其最小值再加1即可。算法会超时，但是也贴一下。

class Solution {
public:
    int jump(vector<int>& nums) {
        int t[nums.size()];
        t[nums.size()-1]=0;
        for(int i=nums.size()-2; i>=0; i--){
            if(nums[i]==0){
                t[i] = INT_MAX;
                continue;
            }
            int m = INT_MAX;
            for(int j=1; j<=nums[i] && i+j<nums.size(); j++){
                m = min(m, t[i+j]);
            }
            t[i] = m==INT_MAX ? m: m + 1;
        }
        return t[0];
    }
};

现在考虑改进的算法。发现在计算最小值的过程中有着大量的重复计算，将上一次最小值的结果合理利用起来，减少这些重复计算即可降低算法的时间复杂度。由于要不断求解区间最小值，考虑过使用线段树。但是碍于线段树过于庞杂，最后决定还是从本题出发。

• 当当前点能到达的范围覆盖了扫描的点所能覆盖的范围时，就可以直接跳过扫描到的这个点，直接使用这个点到达终点的步数就能代表其步长范围内的点到达终点步长的最小值
• 使用这个算法时要注意对于最后一个点的处理，否则可能使得结果比答案大1或者陷入死循环

实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int t[nums.size()];
        t[nums.size()-1]=0;
        for(int i=nums.size()-2; i>=0; i--){
            if(nums[i]==0){
                t[i] = INT_MAX;
                continue;
            }
            int m=INT_MAX, j=1;
            while(j<=nums[i] && i+j<nums.size()){
                if(nums[i]-j>=nums[i+j]){
                    m = min(m, t[i+j]-1);
                    m = max(0, m);//in case i+j represents the destination
                    j += max(1, nums[i+j]);
                }
                else{
                    m = min(m, t[i+j]);
                    j += 1;
                }
            }
            t[i] = m==INT_MAX ? m: m + 1;
        }
        return t[0];
    }
};

思考

这题给我的成就感很大。我觉得自己对于算法的理解加深了。当初第一次看到kmp算法时，我觉得这简直是天才的想法。现在我开始觉得自己也能够取设计类似的算法来降低时间复杂度了，开心。