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.

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

这个题目因为是问的yes/no,然后跟坐标有关(也就是说如果数组里面有数字互相调换了答案就不一样了),很有可能是dynamic programming,这里用动态规划来做。f(i) 表示能否跳到该点,function 用
f(i) = true if f(j) and nums[j] >= i - j (for loop), 一旦有就break,这里可以稍微improve一点时间上的效率。
T: O(n^2) S: O(n)
note:但是在leetcode上面这个会limit time exceed。

Code:
class Solution:
    def jumpGame(self, nums):
        if not nums: return False
        n = len(nums)
        mem = [False] * n
        mem[0] = True
        for i in range(1, n):
            for j in range(0, i):
                if mem[j] and nums[j] >= i - j:
                    mem[i] = True
                    break
        return mem[n - 1]

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄