PHP Program for Minimum number of jumps to reach end

Write a PHP program for a given array arr[] where each element represents the maximum number of steps that can be made forward from that index. The task is to find the minimum number of jumps to reach the end of the array starting from index 0.
If an element is 0, then cannot move through that element.

Examples:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 9 -> 9)
Explanation: Jump from 1st element to 2nd element as there is only 1 step. Now there are three options 5, 8 or 9. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made.

Input: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 10
Explanation: In every step a jump is needed so the count of jumps is 10.

Start from the first element and recursively call for all the elements reachable from the first element. The minimum number of jumps to reach end from first can be calculated using the minimum value from the recursive calls. 

minJumps(start, end) = 1 + Min(minJumps(k, end)) for all k reachable from start.

Step-by-step approach:

• Create a recursive function.
• In each recursive call get all the reachable nodes from that index.
  • For each of the index call the recursive function.
  • Find the minimum number of jumps to reach the end from current index.
• Return the minimum number of jumps from the recursive call.

Below is the implementation of the above approach:

PHP

<?php
// php program to find Minimum 
// number of jumps to reach end

// Returns minimum number of jumps 
// to reach arr[h] from arr[l]
function minJumps($arr, $l, $h)
{
    
    // Base case: when source and
    // destination are same
    if ($h == $l)
        return 0;
    
    // When nothing is reachable
    // from the given source
    if ($arr[$l] == 0)
        return $h+1;
    
    // Traverse through all the points 
    // reachable from arr[l]. Recursively
    // get the minimum number of jumps
    // needed to reach arr[h] from these
    // reachable points.
    $min = 999999;
    
    for ($i = $l+1; $i <= $h && 
            $i <= $l + $arr[$l]; $i++)
    {
        $jumps = minJumps($arr, $i, $h);
        
        if($jumps != 999999 && 
                    $jumps + 1 < $min)
            $min = $jumps + 1;
    }
    
    return $min;
}

// Driver program to test above function
$arr = array(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9);
$n = count($arr);

echo "Minimum number of jumps to reach "
    . "end is ". minJumps($arr, 0, $n-1);
    
// This code is contributed by Sam007
?>