题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

好像应该用贪心算法比较好，所以暂且放置，学到了回到改。

思路：
用动态规划做的，dp[i]保存跳到i需要的最小的步数
往前看，j从i-1开始往前遍历，比较满足跳跃的第j步里哪个最小，就+1。

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(),INT_MAX);
        dp[0]=0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if(nums[j] >= i - j)//说明j可以跳到i的位置
                    dp[i]=min(dp[i],dp[j]+1);//dp[i]保存跳到i需要的最小的步数
            }
        }
        return dp[nums.size()-1];
    }
};