Jump Game II

题目描述

解题方法

方法1 DP

可以和1类似用DP的方法做，但是会有很多重复计算

方法2 greedy

因为这一题要记录走的步数，所以在每一次往前走的时候都要记录下走了几步， 并且要记录每一步达到的范围，因为算下一步的范围的时候就应该只算当前这一步 能够达到的新范围，避免重复计算之前的。

与Patch array有点类似，每一次算出走到当前这一步可以达到的范围，如果这个范围没有到最后index, 就要再走 一步，计算出下一步范围。 注意点：

1. 要keep track of 当前这一步的范围，计算下一步的范围就不要再对之前的范围重复计算
2. 有了assumption是一定可以达到，所以每次一步都会往前，否则就无法达到了

Solution

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        cur_start = 0
        cur_end = 0
        steps = 0

        while cur_start < length - 1:
            steps += 1
            end = cur_end
            for i in range(cur_start, cur_end + 1): # calculate how far current steps can reach
                end = max(end, i + nums[i])
                if end >= length-1:
                    return steps
            cur_start = cur_end + 1
            cur_end = end

        return steps

cur_start和cur_end记录的是当前这一步可以达到的范围

Reference