力扣热题100_贪心算法_45_跳跃游戏

文章目录

• 题目链接
• 解题思路
• 解题代码

题目链接

45. 跳跃游戏 II

给定一个长度为 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]。

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

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

解题思路

    # 贪心算法 与 动态规划算法的区别 ：
    # 贪心算法
        # 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留；
        # 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
    # 动态规划算法：
        # 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；
        # 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解；
        # 3.边界条件：即最简单的，可以直接得出的局部最优解。

    # 举个例子，比如跳到下标 i 最少需要 5 步，即 dp[i] = 5，那么必然不可能出现少于 5 步就能跳到下标 i + 1 的情况，
        # 续：跳到下标 i + 1 至少需要 5 步或者更多步。
    # 既然 dp[i] 是单调递增的，那么在更新 dp[i] 时，我们找到最早可以跳到 i 的点 j，从该点更新 dp[i]。
        # 续：即找到满足 j + nums[j] >= i 的第一个 j，使得 dp[i] = dp[j] + 1。
    # 而查找第一个 j 的过程可以通过使用一个指针变量 j 从前向后迭代查找。
    # 最后，将最终结果 dp[size - 1] 返回即可。

解题代码

class Solution:
    def jump(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [float('inf') for _ in range(size)]
        dp[0] = 0

        j = 0
        for i in range(1, size):
            while j + nums[j] < i:
                j += 1
            dp[i] = dp[j] + 1
        
        return dp[size - 1]

参考资料：datawhalechina