算法题--跳步游戏II

image.png

0. 链接

题目链接

1. 题目

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

2. 思路1：动态规划

dp[i]表示从第0个位置跳到第i个位置的最小步数
则
    dp[0] = 0
    dp[1] = dp[0] + 1
    dp[2] = min{dp[0] + 1, dp[1] + 1}
    ...
    dp[n] = min{dp[0] + 1, dp[1] + 1, ..., dp[i] + 1, dp[n-1] + 1}
min中间的第i项需要满足条件 i + nums[i] >= n - i
时间复杂度O(n^2)
空间复杂度O(n)

3. 代码

# coding:utf8
from typing import  List


class Solution:
    def jump(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [0] * size
        dp[0] = 0

        for i in range(1, size):
            for j in range(i):
                if nums[j] >= i - j:
                    dp[i] = dp[j] + 1
                    break

        return dp[-1]

solution = Solution()
print(solution.jump([2,3,1,1,4]))

输出结果

2

4. 结果

很遗憾，执行超时，这种方法对于稍长的字符串来说，复杂度太高, 理论复杂度高达O(N^2), 所以难以接受

5. 思路2: 贪婪算法

思路1的缺点，是过于执着于过程中的细节，而没有重点抓住目标问题；

目标问题是求出最少的跳跃次数；

很容易想起贪婪算法，从左到右遍历每个位置，对于每个位置，计算该位置的跳跃潜力( 即从该位置最大可以抵达的目标位置)，然后在遍历的过程中，经过比较，记录到目前为止最大可以抵达的目标位置。

要想使得最终跳跃次数最少，最容易想到的是，尽量利用好前面每个跳跃的潜力，这意味着两点：

1. 在当前跳跃的潜力范围内时，不需要增加跳跃次数;
2. 当遇到当前的这一跳，无法抵达目标位置时，则需要将本次跳跃拆分为两次跳跃来完成，这时候选择到目前位置潜力最大的起点作为新的跳跃的起跳点。

6. 代码

class Solution1:
    def jump(self, nums: List[int]) -> int:
        steps = 0
        cur_end = 0
        max_end = 0
        for i in range(len(nums)):
            if i > cur_end:
                cur_end = max_end
                steps += 1
            end = i + nums[i]
            if end > max_end:
                max_end = end

        return steps


solution = Solution1()
print(solution.jump([2,3,1,1,4]))

输出结果

2

7. 结果

image.png