## Solution

### Greedy + DP

class Solution:
    def jump(self, nums: List[int]) -> int:
        # Time complexity: O(n)
        # Space complexity: O(n)
        #  0 1 2 3 4
        # [2,3,1,1,4]
        # [2,4,4,4,8]
        output = 0
        n = len(nums)
        for i in range(1,n):
            nums[i] = max(nums[i] + i,nums[i-1])
        i = 0
        while i < n - 1:
            output += 1
            i = nums[i]
        return output

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 在上次能跳最遠的地方，選擇一個能跳最遠的位置即可
        end = maxPos = ans = 0
        # 一路考慮跳躍路徑到終點，也就是 n - 1 (題目有說)
        for i in range(len(nums) - 1):
            # 篩選出最大跳躍點 
            # i + nums[i] 等同於計算出從當前位置跳躍到其他下標的索引
            maxPos = max(nums[i] + i,maxPos)
            # 等到把所有能跳格子都考慮完了以後，才跳躍
            if i == end:
                end = maxPos # 更新跳躍點
                ans += 1 # 更新跳躍次數
        return ans

## Complexity

- Time complexity: O(n)
- Space complexity: O(1)