Jump Game II

题目描述

解题方法

方法1 DP

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

方法2 greedy

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

1. 要keep track of 当前这一步的范围，计算下一步的范围就不要再对之前的范围重复计算

Solution

class Solution(object):
    def jump(self, nums):
        cur_start = 0
        steps = 0
        cur_end = 0
        length = len(nums)

        while cur_start < length:
            steps += 1
            end = cur_end + 1
            for i in range(cur_start, cur_end + 1):
                end = max(end, i + nums[i])
                if end >= length - 1:
                    return steps
            cur_start = cur_end + 1
            cur_end = end

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

Reference