> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/dp/0055.-jump-game.md).

# 0055. Jump Game

Medium  |  Greedy + DP  |  460 ms (91.12%),  15.2 MB (91.02%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Jump Game](https://leetcode.com/problems/jump-game/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0055-jump-game)

You are given an integer array `nums`. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

**Return `true` *****if you can reach the last index, or***** `false` *****otherwise*****.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= nums.length <= 10^4`
* `0 <= nums[i] <= 10^5`

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

Input: nums = [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.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**The greedy method is more straightforward than the DP method.**\
However, the mindsets for these two methods are the same.
{% endhint %}

Instead of checking from the beginning, **we check whether we could reach the end backward**. If the maximum jump could pass prevIndex, we assign the current position to prevIndex **`if curIndex + nums[i] >= prevIndex: prevIndex = curIndex`**.&#x20;

In the end, we check whether prevIndex equals the starting index **`prevIndex == 0`**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # (base case)
        if len(nums) == 1: return True
        if nums[0] == 0: return False
        
        # ==================================================
        #  Greedy                                          =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        prevIndex = len(nums) - 1
        for i in range(len(nums)-1, -1, -1):
            if i + nums[i] >= prevIndex: prevIndex = i
                
        return prevIndex == 0

        '''
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        dp = [False] * len(nums)
        dp[-1] = True
        
        cur = len(nums) - 1
        for i in range(len(nums)-2, -1, -1):
            if i + nums[i] >= cur:
                dp[i] = True
                cur = i
        
        return dp[0] == True
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean canJump(int[] nums) {
        /* base case */
        if(nums.length == 1) return true;
        if(nums[0] == 0) return false;
        
        boolean dp[] = new boolean[nums.length];
        dp[nums.length - 1]=true;
        
        int cur = nums.length - 1;
        for(int i=nums.length-2 ; i>=0 ; i--) {
            if(i + nums[i] >= cur){
                dp[i] = true;
                cur = i;
            }
        }
        
        return dp[0];
    }
}
```

{% endtab %}
{% endtabs %}