Minimum Jumps

We will recursively find the minimum number of jumps.

Algorithm:

Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.

• Call the function: minimumJumpsHelper(i).
• If i is equal to N-1, return 0.
• Make a variable ‘ans’ that stores the minimum number of jumps needed to reach the last shop from the current shop.
  • Initialize ‘ans’ with a maximum value (INT_MAX).
• Iterate on the shops from (i + 1) to (i + Arr[i]) and update the answer, i.e., ans = min( ans, 1 + minimumJumpsHelper(j) ) (where j denotes the shop, where we jumped).
• Return the ‘ans’.

In the previous approach, we are recalculating the answer to reach the last shop from a shop. We can optimise it by storing the answer for the amount which we have calculated.
 

For example, if the given array is {2, 1, 3, 2, 4}:

We are recalculating the answer for shops {2, 3}.
 

So since there are overlapping solutions, we can store the solution which we have calculated. For this, we will make an array DP to store the answer.
 

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

Algorithm:

• In a recursive state, if we know the answer for the ith shop, then we will directly return the answer.
   
• Let’s say we have a recursive function ‘minimumJumpsHelper’ which will return the minimum number of jumps to reach the last shop.
  • Make an array DP of size N, initialize it with -1.
  • Call the function: minimumJumpsHelper(i).
    • If i is equal to N, return 0.
    • If DP[i] is not equal to -1, return DP[i]
    • Make a variable ‘ans’ that stores the minimum number of jumps needed to reach the last shop from the current shop.
      • Initialize ‘ans’ with a maximum value (INT_MAX).
    • Iterate on the shops from (i + 1) to (i + Arr[i]) and update the answer, i.e., ans = min( ans, 1 + minimumJumpsHelper(j) ) (where j denotes the shop, where we jumped).
    • Update DP[i], DP[i] = ans.
    • Return the ‘ans’.

Make an array DP of size N to store the answer.
 

DP[i] denotes the minimum number of jumps needed to reach the last shop from the ith shop.

• DP[N - 1] = 0.
• Initialize all other values with a maximum value (INT_MAX).
• Now iterate on shops from N - 2 to 1
  • Let ‘i’ denote the current shop.
  • Iterate on the shops where we can jump from the ith shop, i.e., from (i + 1) to (i + Arr[i]).
    • Update DP[i], DP[i] = min(DP[i] , 1 + DP[j]) (where j denotes the shop, where we jumped).
• Return DP[0] as the answer.

In this approach, we will calculate the farthest shop we can reach from shop 0 with x number of jumps.
 

For example, if the given array is {2, 3, 1, 2, 1} :

For x=1, we can reach shop 2 (shop 0 -> shop2).

For x=2, we can reach shop 4 (shop 0 -> shop1 -> shop 4)

Hence, we require a minimum two jumps to reach the last shop.
 

Algorithm:

• Make three variables ‘maxReach’, ‘jumpsTaken’, and ‘stepsLeft’.
  • ‘jumpsTaken’ denotes the number of jumps taken.
  • ‘maxReach’ denotes the farthest shop we can reach with ‘jumpsTaken’ number of jumps.
  • ‘stepsLeft’ denotes the number of steps we can still take (1 step means moving from shop i to shop (i + 1)).
• Initialise variables:
  • jumpsTaken = 1
  • maxReach =  Arr[0]
  • stepsLeft = Arr[0]
• Iterate on the shops from shop 1 to N - 2, let i denote the current shop.
  • Update ‘maxReach’, maxReach = max(maxReach, i + Arr[i]).
  • Decrement ‘stepsLeft’ by 1, stepsLeft = stepsLeft - 1.
  • If stepsLeft is equal to 0:
    • Increment ‘jumpsTaken’ by 1, jumpsTaken = jumpsTaken + 1.
    • If i is greater than or equal to ‘maxReach’, then we cannot jump from shop i to any other shop, so we will return -1.
    • Else, stepsLeft = maxReach - i.
• Return ‘jumpsTaken’.