Jump Game

• For each index, we find all possible locations we can jump to i.e if we are currently at an index ’i’ and ‘ARR[i]’ = k then we recursively find the answer for all indices from i + 1 to i + k and take the minimum of the answer and add 1 to it to find the minimum number of jumps to reach index last index from index ‘i’.
• For example, Consider the array : 2, 3, 1, 4
• We will have the following recursion tree:
• We can see the arrows in red signify the least number of jumps to reach the last index. In this case, 2 paths are possible each with 2 jumps hence we return 2.

Keeping the above example in mind, we can write the following Recursive solution:

• If the current index is the last index return 0
• Let ‘CURRIDX; be the index we are currently at and trying to reach the last index from ‘CURRIDX’ in a minimum number of jumps. And ‘MINJUMP’ be the minimum number of jumps needed.
• Take a loop from ‘i = 1’ to arr[CURRIDX]’ and find the answer for all possible jumps from the current index
• Try all possible jumps from the current index(a store that in a variable ‘CURRANS’ and recursively find the minimum of all possible jumps.
• After each iteration, update the variable ‘MINJUMP’ which stores the minimum number of jumps needed to reach the last index.
• Finally, return the value of ‘MINJUMP’.

• From the recursion tree in the previous approach, we can easily see that the problems have the property of overlapping subproblems hence we can use the idea of Dynamic Programming to store the results of previous subproblems to reduce our time complexity.
• For memoization, we create an array ‘DP’ where DP[i] stores the minimum number of jumps required to reach the last index from the ‘i-th index’ where 0 <= ‘i’<  n.

Keeping in mind the above idea, we can use the following approach:

• Make a recursive function which takes in 3 parameters current index, given sequence and an array ‘DP’.
• If the current index is equal to the size of array -1 (-1 for 0 based indexing.) we return 0 as we don’t need to jump at all as we are already at the destination index.
• Otherwise, we will try all possible jumps, i.e from a jump of 1 index to the jump of the maximum possible index and recursively calculate all the values.
• Finally, we calculate the minimum of all the values and store it in our ‘DP’ array.

• Since we are interested in only the minimum amount of jumps we can come up with a greedy solution.
• As an example consider the sequence 5,9,3,2,1,0,2,3,3,1,0

    Now, think about the following,

    To reach the last index we try to reach the minimum index from which we can reach the last index.

        -- Now what is the minimum index from which we can reach the last index in one jump?

          From  -- index 0 we can at max go  0 + 5 = 5, not 11

          From   -- index 1, we can at max go 1 + 9 = 10, not 11

          From  -- index 2, we can at max go 2 + 3 = 5, not 11

          From -- index 3,we can at max go 3 + 2 = 5,not 11

          From   -- index 4 we can at max go, 4 + 1 = 5, not 11

          From  -- index 5, we can at max go 5 + 0 = 5, not 11

          From   -- index 6, we can at max go 6 + 2 = 8, not 11

          From -- index 7, we can at max go 7 + 3 = 10, not 11

          From   -- index 8,  we can at max go 8 + 3 = 11, yes!

          Thus we have to first reach index 8.

        --  Now what is the minimum index from which we can reach index 8 in one jump?

            -- index 0,we can at max go 0 + 5 = 5, no

            -- index 1, we can at max go 1 + 9 = 10, yes

            Thus we have to first reach index 1.

        -- Now what is the minimum index from which we can reach index 1 in one jump?

            -- index 0,we can at max go 0 + 5 = 5, yes

           Therefore, 3 jumps in total.

Keeping in mind the above example, we can use the following approach:

• Take the variables 'MINJUMP' to store the minimum number of jumps,’curEnd’ to store the farthest index we can go from the current index and 'CURFARTHEST' to store the farthest we can go with the help of elements we have encountered till now.
• We initialise the value of 'CUREND' and 'CURFARTHEST' to be 0.
• Let's say the range of the current jump is ['CURBEGIN', 'CUREND'].
• 'CURFARTHEST' is the farthest point that all points in ['CURBEGIN', 'CUREND'] can reach.
• Once the current index ‘i’ reaches the 'CUREND' we have reached the maximum possible index we could have reached in 1 jump, therefore, we trigger another jump.
• We then set the new 'CUREND' with 'CURFARTHEST', until 'CURFARTHEST' is equal to the last index of the given sequence.