class Solution {
    int[] arr;

    public int jump(int[] nums) {
        arr = new int[nums.length];
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return 0;

        return jumpRec(nums, 0);
    }

    public int jumpRec(int[] nums, int index) {
        // arr can have either:
        //  the minimun number of jumps
        //  the initialized value
        //  or an out out range value
        // NOTE: by using 1001 (check the problem description), instead of Integer.MAX_VALUE, we avoid overloading problems
        if(arr[index] != 0 && arr[index] != 1001)
            return arr[index];
        if(index == nums.length-1) {
            return 0;
        }
        // NOTE: by using 1001 (check the problem description), instead of Integer.MAX_VALUE, we avoid overloading problems
        if(index > nums.length-1) {
            return 1001;
        }
        // NOTE: by using 1001 (check the problem description), instead of Integer.MAX_VALUE, we avoid overloading problems
        int thisMin = 1001;
        for(int i=Math.min(index+nums[index], nums.length-1); i > index; i--) {
            int jumpsFromThisI = 1 + jumpRec(nums, i);
            thisMin = Math.min(thisMin, jumpsFromThisI);
        }
        // store the minimum number of jumps from this index
        arr[index] = thisMin;
        return arr[index];
    }
}