Find minimum number of jumps to reach the end

The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.

We can see that in each recursive call only the value of "i" changes, so we can store and reuse the result of a function(..i..) call using an array.

The array will store a particular state (..i.) if we get it the first time.

Now, if we come across the same state (..i..) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.

The time complexity of this solution is (n).

In addition, O(n) auxiliary space was used by the table.

We can solve this problem with recursion.

The idea is to check for the minimum number of jumps required from each element and return the minimum.

The recursion will start from the "0th" index until a dead node "arr[i]==0" is reached or the jump reaches the end.

We can use an inner "for" loop to check for each possible jump and return "minimum + 1" in each recur.

In case a dead node "arr[i]==0" is reached, we need to omit that path - return "Integer.MAX_VALUE", so that this is omitted in the "min()" function.

We also need to handle overflow in case "Integer.MAX_VALUE" is returned from the recursive call. This can be handled by adding "+1" only after the check.

In the end, we also need to take care of the "unreached" scenario. This can be achieved by returning "-1" if the end result is "Integer.MAX_VALUE".

The time complexity of this solution is exponential O(n^2).

In addition, O(n) auxiliary space was used by the recursion stack.