[LeetCode]45. 跳跃游戏 II（Jump Game II）
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [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/
