題目描述

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.

給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置秆剪。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度赊淑。

你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。

題解

首先想到的解法是：聲明一個數(shù)組dp(size, size), dp[i]表示達到坐標i的最小跳數(shù)仅讽。

使用雙層循環(huán)陶缺，第一層遍歷數(shù)組，第二層在nums[i]范圍內遍歷洁灵，表示在i的可及范圍內進行更新dp[i+j], dp[i+j]=min(dp[i+j], dp[i]+1)饱岸；但是要保證i+j的有效性。一旦i+j == size-1,及時終止循環(huán)徽千。

代碼：

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

這種方法對于一般的測試集能通過苫费，對于特別變態(tài)的，2500-0的數(shù)組會導致超時【ps：可以針對這個測試用例單獨處理双抽，能accept百框；畢竟不符合題意，時間復雜度太高】牍汹。

另一種方法和這個方法類似：不使用雙層循環(huán)铐维。使用兩個變量cur, next分別表示當前窗口的右邊界，下個窗口的右邊界柑贞；遍歷數(shù)組時方椎，不斷更新next窗口的右邊界；當當前位置i超出當前窗口的右邊界時钧嘶，更新cur棠众，更新jumps。循環(huán)結束，返回jumps闸拿；或者當更新cur>=size-1數(shù)組邊界時空盼，即使返回。

代碼：

class Solution {
public:
    int jump(vector<int>& nums) {
        int size = nums.size(), cur = 0, next = 0, jumps = 0;
        
        for (int i=0; i< size; ++i){
            if (i > cur){
                cur = next;
                ++jumps;
                // if (cur >= size-1) break;
            }
            next = max(next, i + nums[i]);
        }
        
        return jumps;
    }
};

Reference

https://www.cnblogs.com/grandyang/p/4373533.html