leetcode55 Jump Game 解題概念

題目會給一組正整數數列，我們會從第一個數字開始，數字顯示我們最多可以行走的距離，我們要確定該數列是否有可能可以抵達最終一個數字。

倒推法

這邊我們將目標設定為最後一個位置，然後我們從最後一個數字往前找，只要有滿足『位置+行走距離』大於等於『目標』的情況時，我們就會更新該位置為新的『目標』

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        goal = len(nums)-1
        for idx in range(goal,-1,-1):
            val = nums[idx]
            if idx+val >= goal:
                goal = idx
        
        return True if goal == 0 else False

最遠距離

這個概念是我們盡可能地往遠處走，我們記錄每個點最遠可以行走的距離，只要還沒有超過當前的最遠距離時，我們就會持續往下一個位置移動，並且更新最遠行走距離。

class Solution:

     def canJump(self, nums: List[int]) -> bool:
        
        if len(nums) == 1:
            return True
        
        farthest = nums[0]
        idx = 0
        while idx < len(nums)-1:

            if farthest >= len(nums)-1:
                return True
            
            idx +=1
            if idx > farthest:
                return False
            if idx+nums[idx]>farthest:
                farthest = idx+nums[idx]