[数据结构与算法]leetcode45.跳跃游戏Ⅱ（中等）

leetcode55.跳跃游戏：https://blog.csdn.net/zhangjiaji111/article/details/120659495
方法一：贪心
具体思路：当前的位置跳的位置为：下下次可以跳得更远的位置。 通过局部最优得到全局最优解。

class Solution {
public:
    int jump(vector<int>& nums) {
        
        int n = nums.size(), index = 0, ans = 0; 
        if (n == 1) return 0;
        while (1) {
            int tmp = INT_MIN;
            int tmp2 = index;
            for (int i = tmp2 + 1; i <= tmp2 + nums[tmp2]; ++i) {
                if (i == n - 1) return ans + 1;
                if (i + nums[i] > tmp) {
                    tmp = max(tmp, i + nums[i]);
                    index = i;
                }
            }
            ans++;
        }
        return ans;
    }
};

方法二：dp
具体思路：得到i下标的最小跳跃数dp[i]后，对接下来dp[i+1]到dp[i+nums[i]]有影响，不断更新最小跳跃数

class Solution {
public:
    int jump(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j <= i + nums[i] && j < n; ++j) { //j可能会越界
                dp[j] = min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
};

易错点：j可能会越界，加上&& j < n！！！