# Problem 55: Jump Game

> <https://leetcode.com/problems/jump-game/>

## 思路

1. dynamic programming 的思路在判断大的数据的时候超时，这时用 greedy programming
2. 像头标枪一样，我不关心最后我是否到最后一个index了，先闷头扔一下，一直维护到最后一次，然后比较我最后所在的位置和数组最后一个的位置之间的关系

* Update: 这个解法更容易理解。用 max 来记录当前最远能调到的距离，如果 i < max，说明无论如何也打不到，返回 false。&#x20;

```java
public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > max) return false;
            max = Math.max(max, nums[i] + i);
        }

        return true;
    }
}
```

```java
public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }

        int n = nums.length;
        int farest = nums[0];
        for (int i = 1; i < n; i++) {
            if (i <= farest && i + nums[i] >= farest) {
                farest = i + nums[i];
            }
        }

        return farest >= n - 1;
    }
}
```

## 易错点

1. dp的做法

   ```java
   public class Solution {
    public boolean canJump(int[] A) {
        boolean[] can = new boolean[A.length];
        can[0] = true;

        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }

        return can[A.length - 1];
    }
   }
   ```

   这个做法的时间复杂度是O(n^2)，当数据过大时，会超过时间要求
2. 判断的条件

   ```java
   if (i <= farest && i + nums[i] >= farest) {
     farest = i + nums[i];
   }
   ```

   这两个条件是缺一不可的。如果没有第一个条件，有可能是i很大，已经超过了farest
3. 比较条件

   ```java
   return farest >= n - 1;
   ```

   开始的时候，错误地

   ```java
   return farest >= nums[n - 1];
   ```

   这里我们要比的是farest最后的index，而nums\[n - 1]表示的是**最后还能再跳几个值**。他们是明显不同的。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuyang89116.gitbook.io/my-leetcode-book/chapter_5_dynamic_programming/sequence-lei-xing/problem_55_jump_game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.