跳跃游戏

题目源自Leetcode: 跳跃游戏II-leetcode

给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置.

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2.   从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组的最后一个位置.

思路1: 动态规划

我们令 dp[i] 为 从第 i 个位置到最后一个位置所需的跳跃次数. 显然, 若数组长度为 n , dp[n] = 0. 对于其他的位置 i, 假设 j 是任意一个 i 能跳到的位置, dp[i] 应为 所有 dp[j] 的最小值再加1. 即:

\[ dp[i]=\left\{\begin{matrix} 0 & i = n \\ \underset{j\in \{all\}}{\min}\{dp[j]\}+1 & i < n \end{matrix}\right. \]

这里的 {all} 表示 所有在位置 i 能跳到的位置.

有了这个递归式我们很快能写出一个动态规划算法:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [float('inf')] * len(nums)
        dp[-1] = 0
        for i in xrange(len(nums) - 2, -1, -1):
            to = min(i + nums[i], len(nums) - 1)
            dp[i] = min(dp[j] for j in xrange(i, to + 1)) + 1

        return dp[0]

这个算法本身是正确的, 但是无法通过 Leetcode 提交, 因为会超出时间限制

思路2: 贪心算法

我们可以选用这样一种策略: 对于每个位置 i, 都能跳到若干个位置; 总是在这若干个位置中选择能跳得最远的位置进行跳跃.

以 [2,3,1,1,4] 为例: 对于位置 i = 0, 能跳到 1 和 2 这连个位置; 如果选择跳到位置 1, 那么最远可以跳到 5; 如果选择跳到位置2, 那么最远可以跳到 4. 因此我们选择跳到位置 1. 接下来对于 i = 1, 再作同样的操作即可. 根据这个思路, 我们可以写出这样一个贪心算法:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        steps = 0
        end = 0
        maxPos = 0
        for i in xrange(len(nums) - 1):
            maxPos = max(nums[i] + i, maxPos)

            if i == end:
                end =  maxPos
                steps += 1

        return steps