1340. Jump Game V [TODO]

 一刷 06/2022

[TODO] Segment Tree / Stack

Version #1 DFS + Memorization

Time O(Nd)

Space O(N)

Runtime: 21 ms, faster than 28.93% of Java online submissions for Jump Game V.

Memory Usage: 48.3 MB, less than 23.90% of Java online submissions for Jump Game V.

class Solution {

    public int maxJumps(int[] arr, int d) {

        int[] dp = new int[arr.length];

        int max = 0;

        for (int i = 0; i < arr.length; i++) {

            max = Math.max(max, dfs(arr, i, d, dp));

        }

        return max;

    }

    

    // Return the max step that can jump from current index

    private int dfs(int[] arr, int index, int d, int[] dp) {

        if (index < 0 || index >= arr.length) {

            return 0;

        }

        if (dp[index] > 0) {

            return dp[index];

        }

        int max = 0;

        for (int offset = 1; offset <= d; offset++) {

            if (index + offset >= arr.length || arr[index + offset] >= arr[index]) {

                break;

            }

            max = Math.max(max, dfs(arr, index + offset, d, dp));

        }

        for (int offset = 1; offset <= d; offset++) {

            if (index - offset < 0 || arr[index - offset] >= arr[index]) {

                break;

            }

            max = Math.max(max, dfs(arr, index - offset, d, dp));

        }

        dp[index] = 1 + max;

        return dp[index];

    }

}