# 55 & 45. Jump Game I & II

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*.

**Example 1:**

<pre><code><strong>Input: nums = [2,3,1,1,4]
</strong><strong>Output: true
</strong><strong>Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,1,0,4]
</strong><strong>Output: false
</strong><strong>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.
</strong></code></pre>

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 105`

***My Solutions:***

用一个变量记录在当下可以达到的最远距离。在遍历完数组之后，检查这个最远距离是否达到数组的长度-1（数组最后一个数字）。

```
public boolean canJump(int[] nums) {
    int max = nums[0], len = nums.length;
    if (len == 1) return true;

    for (int i = 1; i < len; i++) {
        if (max < i) return false; // 这一步必须先检查，看当前的位置能否到达
        max = Math.max(max, i + nums[i]);
    }

    return max >= len - 1;
}
```

**45. Jump Games II**

类似的题目，但是要返回 minimum number of jumps to reach nums\[n - 1]. The test cases are generated such that you can reach nums\[n - 1].

**Example 1:**

<pre><code><strong>Input: nums = [2,3,1,1,4]
</strong><strong>Output: 2
</strong><strong>Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,3,0,1,4]
</strong><strong>Output: 2
</strong><strong>Explaination: 从2跳到3，再从3跳到4
</strong></code></pre>

***My Solutions:***

方法1: DP

```
public int jump(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len];

    for (int i = 1; i < len; i++) { // 因为已经站在第一个位置上，所以从第二个位置开始
        
        // 每到达一步需要的最多步数，比如到index1至少需要跳一步；在index4至少需要跳四步
        dp[i] = i; 
        
        for (int j = 0; j <= i; j++) {
            //如果从j位置可以跳到i位置
            if (nums[j] + j >= i) { 
                dp[i] = Math.min(dp[j] + 1, dp[i]);
            }
        }
    }
    
    return dp[len - 1];
}
```

方法2: 贪心。如果想要步数最小，需要每一步都跳的很大。在遍历数组的时候，确定当前最远能跳到的位置，记录为max。如果当前的位置超过了上一次算出的最大位置（lastJumpMax)，那么更新lastJumpMax，同时更新步数，因为必须要多一跳才能继续前进。

```
public int jump(int[] nums) {
    int steps = 0, max = 0, lastJumpMax = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        max = Math.max(max, i + nums[i]);
        if (i == lastJumpMax) {
            lastJumpMax = max;
            steps++;
        }
    }
    return steps;
}
```
