力扣第45题：跳跃游戏 贪心DP（C++）
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 :
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
思路
思考一个问题：如果在位置j不能跳到位置i（j<i），那么j能跳到i+1吗？
注意，在j处能跳到的最远位置是下标j+nums[j]的位置。如果j不能跳到i，那么i就大于这个最远位置。
那么显然j是不能跳到i+1的的。记住这件事，他是求DP时贪心的关键条件。
解题过程
DP数组的实现就不必多说了，无非是dp[i]=dp[j]+1（到i的最少步数是j的步数+1，其中j是前面的所有能跳到i的位置里步数最少的）只是还不知道j是多少而已。
问题来了，对于每一个i，怎么找到前置j？
DP数组一定越来越大，所有我们一定要尽量从前开始找j。
为了跳到i，我们需要找到从前向后第一个j+nums[j]>=i的j。
但是对于每一个i，我们需要每次都从0开始找j吗？
回想到我们的思考：如果j不能跳到i，那自然就不能跳到i+1。
因此，j不需要重置为0：
i+1的前置j一定大于等于i的前置j。
主体部分如下：
for(int i=1,j=0;i<len;i++){
while(j+nums[j]<i)j++;
dp[i]=dp[j]+1;
}
复杂度
时间复杂度: O(n)
空间复杂度: O(n)
复杂度分析：
i会遍历一次数组，他的前置位置j也只会遍历一次数组，时间复杂度是线性级别的。
使用了常量空间的双指针和长度为n的DP数组，空间复杂度是线性级别的。
Code
class Solution {
public:int jump(vector<int>& nums) {const int len=nums.size();vector<int>dp(len,0);for(int i=1,j=0;i<len;i++){while(j+nums[j]<i)j++;dp[i]=dp[j]+1;}return dp[len-1];}
};