Leetcode-45.Jump Game II

Reference

📘 45. Jump Game II

Description 📖

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

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 <= 104
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

Thinking 🤔

• Be aware of the achievability: It's guaranteed that you can reach nums[n - 1].
• Array & F[n] -> DP
• Result of F[n] is stable.
• $F(i)=\{\begin{array}{l}F[i-1](CertainCondition)\\ F[i-1]+1(CertainCondition)\end{array}$

Solution ✏️

DP

DP

Definition: F(n), Minimum steps to achieve nums[n - 1]

Take a few examples, it’s easy to infer that the result of F(n) is gradually increasing.

2	3	0	5	0	1
0	1	1	2	2	3

We get the DP formula:

$$F(i)=\{\begin{array}{l}F[i-1](CertainCondition)\\ F[i-1]+1(CertainCondition)\end{array}$$

So we need to find the connection —— the Certain Condition.

When it pass by certain position, the steps may be extra. So we use a array cache to hold how many steps left when passing current index.

Definition: P(n), Possible left available steps when passing by index n.

So we get this formula

$$F[i]=\{\begin{array}{l}F[i-1](P[i-1]>0)\\ F[j]+1(P[i-1]==0\mathrm{\&}\mathrm{\&}nums[j]+j\ge i(j=0,1,2\dots i-1))\end{array}$$

Why search from begin?

Because $F[i]\le F[i-1]$, so the steps is no more than searching from end if we search from begin.

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

Complexity Analysis

Time-Complexity: $O(N^2)$

Zone-Complexity: $O(N)$

It’s actually kind like this way given by Leetcode

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

// Author：力扣官方题解
// Link：https://leetcode.cn/problems/jump-game-ii/solutions/230241/tiao-yue-you-xi-ii-by-leetcode-solution/

DP & Greedy

Max Achievable Position

Use part thoughts of Greedy

What if we plan most achievable positions for each index?

Core: Greedy Thought

If each time we take a furthest jump from current point, then we will get the destination with minimum steps

Definition: L[i], most achievable positions starting from index i.

	2	3	1	1	4
F[i]	0	1	1	2	2
L[i]	2	4	4	4	8

It’s actually connected with previous results. So combined with DP notion.

$$L[i]=max(i+nums[i],L[i-1])$$

To get F[n]:

1. Starting from 0, jump to next position by nums[i]
2. Step added in each jump.
3. When reaching nums[n - 1], we get the final count.

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int[] maxReach = new int[nums.length];
        maxReach[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxReach[i] = Math.max(i + nums[i], maxReach[i - 1]);
        }
        int count = 0;
        for (int i = 0; i < nums.length - 1;) {
            i = maxReach[i];
            count++;
        }
        return count;
    }
}

Complexity Analysis

Time-Complexity: $O(N)$

Zone-Complexity: $O(N)$

Optimization

Talking to DP, there is always possible optimzation using Rolling Array, it’s kind of an old friend.

What is Rolling Array?

In brief, it’s a kind of optimization, which aims to reducing the dimension of Zone-Complexity.

We need to find out extra meaningless usage of space, and try to optimize.

Usually 2-dimension to 1-dimension, 1-dimension to Constant Level.

So we can observe that, we only use maxReach[i - 1] and as to calculate count, we actually use last numbers from maxReach[] which is just lower than current maxReach[i]. So we can optimize Zone to O(n) Complexity.

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int lastReach = nums[0];
        int lastMaxReach = nums[0];
        int count = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            int currentReach = i + nums[i] > lastReach ? i + nums[i] : lastReach;
            if (i == lastMaxReach) {
                count++;
                lastMaxReach = currentReach;
            }
            lastReach = currentReach;
        }
        return count + 1;
    }
}

Complexity Analysis

Time-Complexity: $O(N)$

Zone-Complexity: $O(1)$

Reflection 🤔

• Even the DP formula/model for a question can be mutiple. It can be inverse Sequential or Reverse. But may produce different efficiency. So if a formula to solve a problem is not good as you think, then try another way.
• Pay attention to the importance of Rolling Array again when optimize DP problems, it’s quite effective! 👍