题目描述
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
解题思路
解法一:DFS。时间复杂度太高。
解法二:DP。dp[i] 表示跳到 i 位置需要的最少步数,它取决于前面所有能够跳到 i 处的位置。
- 解法三:贪心。对于当前位置,对他能跳到最远的位置,若之前没有被跳到,则状态更新。也就是:从一个位置跳到它能跳到的最远位置只要一步,后面的位置上如果也能跳到,则肯定比当前花费的步数多。
代码
Python 3.6
解法一:DFS(超时)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution: def __init__(self): self.min_step = float("inf") def jump(self, nums: List[int]) -> int: self.__dfs(0, len(nums), nums, 0) return self.min_step def __dfs(self, left, size, nums, step): if step >= self.min_step: return if left >= size - 1: self.min_step = min(step, self.min_step) return for j in range(1, nums[left] + 1): step += 1 self.__dfs(left + j, size, nums, step) step -= 1
|
超出时间限制
解法二:动态规划(超时)
1 2 3 4 5 6 7 8 9 10
| class Solution: def jump(self, nums: List[int]) -> int: length = len(nums) dp = [float("inf")] * length dp[0] = 0 for i in range(1, length): for j in range(i): if nums[j] >= i - j: dp[i] = min(dp[i], dp[j] + 1) return dp[-1]
|
超出时间限制
解法三:贪心
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution: def jump(self, nums: List[int]) -> int: length = len(nums) if length == 1: return 0 steps = [0] * length for i in range(length): for j in range(nums[i], 0, -1): if i + j >= length - 1: return steps[i] + 1 elif steps[i + j] == 0: steps[i + j] = steps[i] + 1 else: break return steps[-1]
|
执行用时 : 168 ms
内存消耗 : 15.9 MB
参考
https://leetcode-cn.com/problems/jump-game-ii/solution/tan-xin-suan-fa-by-powcai/