55. 跳跃游戏(Medium)

题解

视频题解：https://www.bilibili.com/video/BV1wA411b7qZ?p=13

Python示例

Bottom To Top 使用递归自底向上

# 超时 75/76
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        def jump(start):
            if meno[start] == 1: return True 
            elif meno[start] == -1: return False 

            # meno[start] == 0 状态不确定
            end = min(start + nums[start], len(nums) - 1)
            for i in range(start + 1, end + 1): # 至少跳一步，不然死循环
                if jump(i): 
                    meno[i] = True 
                    return True 
            meno[start] = -1
            return False 

        meno = [0] * len(nums) # bottom to top
        meno[-1] = 1
        
        return jump(0)

Bottom To Top 动态规划

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [0] * len(nums) # dp 记录的是每位的状态
        dp[0] = 1
        for i in range(1, len(nums)): # 求出第i个位置是否可达
            for j in range(i)[::-1]: # 从 i - 1 到 0 倒叙遍历
                if dp[j] and i - j <= nums[j]:
                    dp[i] = 1 
                    break # 剪枝
        return bool(dp[-1]) # 看最后一位元素是否可达

// go 是不会超时
func canJump(nums []int) bool {
    dp :=  make([]int, len(nums))
    dp[0] = 1
    for i := 1; i < len(nums); i++ {
        for j:= 0; j < i; j++ {
            if i - j <= nums[j] && dp[j] == 1{ // j 可达 而且 可以跳到
                dp[i] = 1 
                break 
            }
        }
    }
    return dp[len(nums) - 1] == 1 
}

Top To Buttom 动态规划

# 超时 75/76
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [0] * len(nums)
        dp[-1] = 1
        for i in range(len(nums) -2, -1, -1): 
            for j in range(i + 1, max(i + nums[i] + 1, len(nums))):
                if dp[j] == 1:
                    dp[i] = 1
                    break
        return bool(dp[0])

贪心法--最优解

视频教程：https://www.bilibili.com/video/BV1wA411b7qZ?p=13

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxJamp = len(nums) - 1 # maxJump 代表的点一定是可达的，显然最后一个点一定是可达的
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] + i >= maxJamp: # 只要我能跳到可达的点，那我一定也是可达的
                maxJamp = i 
        return maxJamp == 0

func canJump(nums []int) bool {
    maxJump := len(nums) - 1
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] + i >= maxJump { // i 能够跳到
            maxJump = i
        } 
    }
    return maxJump == 0 
}