# **Leetcode筆記(Jump Game)**

:::info
:information_source: 題目 : Jump Game, 類型 : dynamic programming , 等級 : medium
日期 : 2023/04/24，2023/06/13，2023/09/29，2023/12/09
:::

### 嘗試

出現錯誤
RecursionError: maximum recursion depth exceeded while calling a Python object
搞錯題目，是只要小於該數字的步數都可以跳

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        tmp = 0
        
        def dfs(tmp):
            if tmp >= len(nums):
                return False
            tmp = tmp + nums[tmp]
            if tmp == len(nums) - 1:
                return True
            dfs(tmp)
        
        return dfs(0)    

2023/06/13
dp[i]的意義為可否到達離自己最近的True
從後面開始想，初始化將最後一個dp標示為True
只要a[i]的步數 大於 其與最近True的距離，那就代表可以跳到該True
如果最後dp[0]為True，那就是可從第一位走到最後一位

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        dp = [False] * l
        # 最後一個初始化
        last = l - 1
        dp[last] = True

        for i in range(l - 2, -1, -1):
            if nums[i] >= last - i:
                dp[i] = True
                last = i
        
        return dp[0]

2023/07/22
如果左右兩個index之間的距離，小於nums[左邊index]的數值，那就代表可以成功跳過去
如果可以成功跳過去，就要更新右邊index，因為此時目標已經改變

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        _len = len(nums)
        target = _len - 1

        for i in range(_len - 2, -1, -1):
            if nums[i] >= target - i:
                target = i
                if target == 0:
                    return True
        return False

2023/09/29
自創dp，從前面開始跳

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        dp = [False] * l
        dp[0] = True
        
        for i, n in enumerate(nums):
            if dp[i]:
                for j in range(1, n + 1):
                    if i + j < l:
                        dp[i + j] = True
            if dp[l - 1]:
                return True
        
        return False

2023/12/09

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False] * len(nums)
        dp[0] = True
        # nums = [2,3,1,1,4]
        for i, n in enumerate(nums):
            if dp[-1]:
                return True
            if dp[i]:
                for j in range(1, n + 1):
                    if i + j < len(nums):
                        dp[i + j] = True
        return False

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

---
### **優化**

所谓贪心算法，就是在行动的时候，最大化当前的一步收益。举个下山的例子：选择当前下降程度最高的方向，作为下降的选择，即尽可能地在当前这一步下降最多的高度。

在本题中，我们需要找出当前数字的最远可达位置。

最远可达位置：index + value，当前的位置 + 能跳跃的步数；

時間複雜度O(n)，空間複雜度O(1)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        # 如果len為5 那就是從3看
        for i in range(len(nums) - 2, -1, -1):
            # 大於也可以 代表跳少一點
            if i + nums[i] >= goal:
                # 通過代表一定達到目標
                # 更新目標
                goal = i
        
        if goal == 0:
            return True
        else:
            return False 

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=Yan0cv2cLy8&ab_channel=NeetCode
Provided by. NeetCode

###### tags: `dynamic programming` `medium` `leetcode`