[数据结构与算法]LeetCode·45.跳跃游戏 ||· 贪心·动态规划

链接：https://leetcode.cn/problems/jump-game-ii/solution/-by-xun-ge-v-l2cc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。?

题目

?

示例

?

思路

解题思路
【贪心】
本题要计算最小步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

【动态规划】
定义dp数组

• 含义：dp[i]表示从下标0到下标i所以的最小跳跃步数
• 初始化：因为需要动态更新dp，所以初始化应该为最大值，才能保存最小值
• 动态状态方程：dp[i] = MIN(dp[i],dp[j]+1);

如何判断从下标0到下标i所以的最小跳跃步数，使用双指针，一个指向当前位置i，一个从0开始遍历，判断需要多少步才能到当前位置，每次保存最小步数。

代码

【贪心】

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int jump(int* nums, int numsSize){ 
    int curDistance = 0;    // 当前覆盖的最远距离下标
    int ans = 0;            // 记录走的最大步数
    int nextDistance = 0;   // 下一步覆盖的最远距离下标
    for (int i = 0; i < numsSize - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
        nextDistance = MAX(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
        if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
            curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
            ans++;
        }
    }
    return ans;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/jump-game-ii/solution/-by-xun-ge-v-l2cc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

【动态规划】

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int jump(int* nums, int numsSize)
{
    //定义dp数组
    int dp[numsSize];
    dp[0] = 0;
    //双重遍历
   
    for(int i =1; i< numsSize; i++)
    {
        dp[i] = INT_MAX;//初始化最大值
        for(int j = 0; j < i; j++)
        {
            if(j + nums[j] >= i)
            {
                dp[i] = MIN(dp[i],dp[j]+1);//更新dp数组，保存最小值
            }
        }
    }
    return dp[numsSize-1];
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/jump-game-ii/solution/-by-xun-ge-v-l2cc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。