Jump Game V

This approach significantly improves upon the brute-force method by using memoization, a key technique in dynamic programming. We observe that the recursive function dfs(i) is called multiple times with the same index i, leading to redundant computations. By storing the result of dfs(i) the first time it's computed and reusing it for subsequent calls, we can reduce the time complexity from exponential to polynomial. This is also known as top-down dynamic programming.

• Create a memoization array memo of size n, initialized to 0. memo[i] will store the result of the longest path starting from i.
• Define a recursive function dfs(i).
• Inside dfs(i), first check if memo[i] is non-zero. If so, a result has been computed, so return memo[i].
• Initialize res = 1.
• Explore jumps to the right (from i+1 to min(i+d, n-1)). Stop if a blocking element (arr[j] >= arr[i]) is found. For each valid jump to j, update res = max(res, 1 + dfs(j)).
• Explore jumps to the left (from i-1 to max(0, i-d)) similarly.
• Store the final result in memo[i] = res and return it.
• The main function calls dfs(i) for all i from 0 to n-1 and returns the maximum value obtained.

We augment the recursive solution with a memoization table, typically an array memo, to store the results of subproblems. memo[i] will hold the maximum number of indices that can be visited starting from index i.

The algorithm is as follows:

1. Initialize a memo array of the same size as arr with a sentinel value (e.g., 0) to indicate that the result for that index has not been computed yet.
2. Modify the dfs(i) function. At the beginning of the function, check if memo[i] already contains a computed result. If it does, return that value immediately.
3. If memo[i] has not been computed, proceed with the same logic as the brute-force approach: calculate the maximum path length by exploring valid jumps to the left and right and making recursive calls.
4. Once the result for i is computed, store it in memo[i] before returning.
5. The main loop still iterates through all indices i as starting points, calling the memoized dfs(i) and tracking the overall maximum.

This ensures that the longest path for each index is calculated exactly once.

class Solution {
    int[] memo;
    int[] arr;
    int d;
    int n;

    public int maxJumps(int[] arr, int d) {
        this.n = arr.length;
        this.arr = arr;
        this.d = d;
        this.memo = new int[n];
        
        int maxJumps = 0;
        for (int i = 0; i < n; i++) {
            maxJumps = Math.max(maxJumps, dfs(i));
        }
        return maxJumps;
    }

    private int dfs(int i) {
        if (memo[i] != 0) {
            return memo[i];
        }

        int res = 1;
        // Jump to the right
        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }

        // Jump to the left
        for (int j = i - 1; j >= Math.max(0, i - d); j--) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }
        
        memo[i] = res;
        return res;
    }
}