Jump Game

A popular problem in dynamic programming is the jump game problem. The problem is from LeetCode and is defined as follows:

You are given an Array \(A\) containing non-negative integers where \(A[i]\) denotes the maximum number of steps you can take from index \(i\). You start at index 0 and you need to reach the last index of the array. Determine if you can reach the last index.

Jump Game and the possible jumps from each index visualized

Todo

Need to do this for the normal jump game problem https://www.youtube.com/watch?v=Yan0cv2cLy8

brute force is n^n, with memoization it is n^2 and with greedy bottom up it is n the greedy idea comes from the fact that we change end position to the current position if we can reach the end position

Minimum Number of Jumps

The problem can also be changed to rather then just determining if you can reach the last index, determine the minimum number of jumps needed to reach the last index. This problem is also from LeetCode . There is a youtube video that explains the problem and some solutions here .

Todo

Greedy solution is something like a BFS.

An initial idea would be to solve the subproblem of “What is the minimum number of jumps needed to reach index \(i\)?” and then use this to solve the problem of “What is the minimum number of jumps needed to reach the last index?”. So we would define the recursion as follows:

\[\text{minJumps}(i) = \min \{1 + \text{minJumps}(j) \mid 1 \leq j \leq i \land j + A[j] \geq i\} \]

So for each \(i\) we would check all the previous indices and see if we can reach \(i\) from that index. If we can then we would take the minimum number of jumps needed to reach that index and add 1 to it. This results in a time complexity of \(O(n^2)\).


int minJumps(int[] A) {
    int n = A.length;
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (j + A[j] >= i) {
                dp[i] = Math.min(dp[i], 1 + dp[j]);
            }
        }
    }
    return dp[n-1];
}

This is already polynomial but we can do better. Having to look at all previous indices seems like a waste of time. Instead we could store in our DP table at index \(i\) the maximum index we can reach with \(i\) jumps. This way we just need to check if the last index is reachable. The dp table would still be the same size as the worst case is when the array only contains 1’s and we would need to jump to each index. So we would define the recursion as follows:

\[\text{maxIndex}(i) = \max \{j + A[j] \mid 0 \leq j \leq \text{maxIndex}(i-1)\} \]


int minJumps(int[] A) {
    int n = A.length;
    int j = 0;
    int[] dp = new int[n];
    dp[0] = 0;
    // until we can reach the last index
    while (dp[j] < n - 1) {
        j++;
        int maxIndex = dp[j-1];
        // find the maximum index we can reach with j jumps
        for (int i = 0; i <= maxIndex; i++) {
            dp[j] = Math.max(dp[j], i + A[i]);
        }
    }
    return j;
}

This still unfortunately results in a time complexity of \(O(n^2)\) as we have to check all previous indices for each jump to find the maximum index. We can slightly improve this by changing the lower bound to be looked at from \(0\) to \(i-2\) as we know that we can always reach index \(i-2\) with \(i-2\) jumps. So we then just need to look at \(dp[i-1] - dp[i-2]\) elements which results in a time complexity of \(O(n)\).


int minJumps(int[] A) {
    int n = A.length;
    int j = 0;
    // need to initialize to -1 as we are looking at i-2
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 0;
    while (dp[j] < n - 1) {
        j++;
        int maxIndex = dp[j-1];
        // we can start at dp[j-2] as we know we can reach dp[j-2] with j-2 jumps
        for (int i = dp[j-2]; i <= maxIndex; i++) {
            dp[j] = Math.max(dp[j], i + A[i]);
        }
    }
    return j;
}