【Leetcode】45. Jump Game II（动态规划）

待我称王封你为后i 2022-02-25 01:57 193阅读 0赞

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.

**Example:**

Input: [2,3,1,1,4]
    Output: 2
    Explanation: 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.

题目大意：

给出每个位置能够前进的最大长度，返回到达最后一个位置最少需要多少步。

解题思路：

本题常规思路就是更新每个位置到达此处的最小步伐，初始化第一个位置为0（因为我们最初就是站在第一个位置）。

但是会有边界数据，程序超时所以除了上述更新每个位置的步伐之外，还需要在每次更新之后找到下一次更新的起始位置，减去不必要的循环。

样例 2 3 1 1 1 1 4

当从2出发的位置被更新之后，我们发现到达3和1的步伐为一；

从3开始出发之后 1 1 1 位置的步伐被更新为 1 1 1 （每个位置只取最小值）

但是此时我们发现标为红色的两个位置，更新并没有意义。

2 3 **1 1** 1 1 4

所以我们需要进一步找到下一个更新位置。

class Solution {
    private:
        int min(int x, int y){
            return x>y?y:x;
        }
    public:
        int jump(vector<int>& nums) {
            if(nums.size() == 1)
                return 0;
            int ans[nums.size()];
            memset(ans, -1,sizeof(ans));
            ans[0] = 0;
            int idx;
            for(int i = 0;i<nums.size()-1; i++){
                
                for(int j = i+1; j < min(nums.size(), i+nums[i]+1) ; j++){
                    
                    if(ans[j] == -1){
                        ans[j] = ans[i] + 1;
                    }
                    else{
                        ans[j] = min(ans[i] + 1, ans[j]);
                    }
                    
                    if(ans[nums.size()-1]!=-1){
                        return ans[nums.size()-1];
                    }
                    
                }
                idx = 1;
                while(i+idx<nums.size()&& nums[i+idx]+idx <= nums[i]) idx++;
                i+= idx-1;
                
                
            }
            
            return ans[nums.size()-1];
        }
    };