0045. Jump Game II

---

Given an array of non-negative integers nums, 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.

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

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^5

---

解法1

Dynamic Programming.

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        int[] memo = new int[len];
        Arrays.fill(memo, Integer.MAX_VALUE);
        memo[0] = 0;
        
        for(int i = 0; i < len; i++){
            // 在当前位置可以跳的步数
            int n = nums[i];
            // 对于每一个从位置i可以到达的位置而言, 它的值总是在当前值和memo[i]+1间取较小的那个
            for(int j = 1; j <= n && i + j < len; j++ )
                memo[i + j] = Math.min(memo[i + j], memo[i] + 1);
        }
        
        return memo[len - 1] == Integer.MAX_VALUE ? 0 : memo[len - 1];
    }
}