LeetCode刷题：45. Jump Game II

LeetCode刷题：45. Jump Game II

LeetCode中有两道关于Jump Game的题目，分别是

45. Jump Game II https://leetcode.com/problems/jump-game-ii/

55. Jump Game

45. Jump Game II 题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:

You can assume that you can always reach the last index.

算法设计

    public int jump(int[] nums) {
     int temp = 0;
        int dest = nums.length - 1;        // destination index

        while(dest != 0){       // 不断向前移动dest
            for(int i = 0; i < dest; i++){
                if(i + nums[i] >= dest){       // 说明从i位置能1步到达dest的位置
                    dest = i;       // 更新dest位置，下一步就是计算要几步能调到当前i的位置
                    temp++;
                    break;      // 没必要再继续找，因为越早找到的i肯定越靠前，说明这一跳的距离越远
                }
            }
        }
        return temp;
   
    }

提交后，Accepted！

---

 另外一种算法设计

 public int jump(int[] nums) {
    if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = 0, jumps = 0;
        while(end < nums.length - 1){
            int farthest = end;
            for(int i = start; i <= end; i++){ // 本层循环不可漏写！！ 
                if(i + nums[i] > farthest){
                    farthest = i + nums[i];
                }
            }
            start = end + 1;
            end = farthest;
            jumps++;// 跳出说明end >= A.length - 1，此后无需再jump++
        }
        return jumps;

    }

同样提交后，Accepted！

---

尝试动态规划求解，提交了一个版本，代码如下：

 public int jump(int[] nums) {
        // state
        int[] steps = new int[nums.length];

        // initialize
        steps[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            steps[i] = Integer.MAX_VALUE;
        }

        // function
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (steps[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
                    steps[i] = Math.min(steps[i], steps[j] + 1);
                }
            }
        }

        // answer
        return steps[nums.length - 1];

}

提交之后，Time Limit Exceeded

92个用例，通过了91个，1个用例未通过。

需要找找问题出在哪里？

 

---

提交通过的动态规划JAVA代码如下：

class Solution {
    public int jump(int[] nums) {
       int[] dp = new int[nums.length];
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(j + nums[j] >= i) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
        }
        return dp[nums.length - 1];

    }
}