# 0045. Jump Game II
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/jump-game-ii/
## 思路
### 思路一 Greedy Algorithm $O(N)$ $O(1)$
用currEnd记录当前step所能到达的最远的地方
如果超过了currEnd就说明step需要+1
### 思路二 DP $O(N^2)$ $O(N)$
自己想出来的hhh
从尾端开始建dp表格，每个格子存的是这个位置到终点最少跳几步，如果是0的话，则说明这个格子无法到达终点
判断条件如下：
- 如果```nums[i] = 0```，说明到了这个格子只能原地不动，则```dp[i] = 0```
- 如果```nums[i]+i>=nums.length-1```，说明到了这个格子最远可以跳到终点，则```dp[i]=1```
- 如果以上两种条件都不成立，则需要通过回圈遍历经过这个格子所能到达的每一个格子，选他们中 跳到终点所需最少的步数+1 便是dp[i]的值
## Code
### 思路一

class Solution {
    public int jump(int[] nums) {
        int end = 0, step = 0, currEnd = 0;
        for(int i=0; i<nums.length; i++){
            if(currEnd<i){
                step++;
                currEnd = end;
            }
            end = Math.max(end, i+nums[i]);
        }
        return step;
    }
}

### 思路二

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int[] dp = new int[nums.length];
        for(int i = nums.length-2;i>=0;i--){
            if(nums[i] == 0){
                dp[i] = 0;
            }
            else if(nums[i]+i>=nums.length-1){
                dp[i] = 1;
            }
            else{
                int min_jump = Integer.MAX_VALUE;
                for(int j = i+1;j <= nums[i]+i;j++){
                    if(dp[j]!=0 && min_jump>dp[j]) {
                        min_jump = dp[j];
                    }
                }
                dp[i] = min_jump!=Integer.MAX_VALUE?min_jump+1:0;
            }
        }
        return dp[0];
    }
}

## Result
Runtime: 27 ms, faster than **41.04%** of Java online submissions for Jump Game II.
Memory Usage: 39.6 MB, less than **63.39%** of Java online submissions for Jump Game II.