> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/55.-jump-game.md).

# 55. Jump Game

\# Medium

{% hint style="success" %}
From end to beginning of the list to record True status. Two pointer: start, end. start move from previous of end until the element of the list can reach end, record True or False status until start out of index.
{% endhint %}

### Solution:

1. Initilize all variables. end = len(nums)-1, start = len(nums)-2, flag = True (because current status is: from last element to last element, it must be True)
2. Two pointer: start and end move. If distance(end-start) <= nums\[start], end jumps to start, start move to pre-element, set flat=True
3. Using while loop to control the index of start until out of index.&#x20;
4. return result=flag

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-M9taCx4CB3pSLwazv_C%2F-M9tkXEGe0kpi8lyo6gA%2F1592254377186.jpg?alt=media\&token=e99537e5-525f-42e7-ab46-b655fd3572de)

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        end = l-1    # last True index in nums
        start = l-2 # index of start in nums, from start to end to see if possible
        flag = True # current status, List[l-1] -> List[l-1]
        
        while start >= 0:
            if nums[start] >= end - start: # 需要的步数是否能够到达end
                end = start
                flag = True
            else:
                flag = False
            start = start-1
        
        return flag
```

{% endtab %}

{% tab title="Java(笨DP)" %}

```java
class Solution {
    public boolean canJump(int[] nums) {
        boolean[] canReach = new boolean[nums.length];
        Arrays.fill(canReach, false);
        canReach[0] = true;
        
        for(int i = 0; i < nums.length; i ++) {
            if(!canReach[i])
                continue;
            for(int x = 1; x <= nums[i] && i+x < nums.length; x ++) {
                canReach[i+x] = true;
                if(i+x == nums.length - 1)
                    return true;                      
            }
        }
        
        return canReach[nums.length - 1];
    }
}
```

{% endtab %}

{% tab title="Java(O(n))" %}

```java
class Solution {
    public boolean canJump(int[] nums) {
        int lastPosi = nums.length - 1;
        for(int i = nums.length - 1; i >= 0; i --) {
            if(i + nums[i] >= lastPosi)
                lastPosi = i;
        }
        return lastPosi == 0;
    }
}
```

{% endtab %}
{% endtabs %}