Dada uma array de inteiros onde cada elemento representa o número máximo de etapas que podem ser feitas a partir desse elemento. Escreva uma função para retornar o número mínimo de saltos para chegar ao final da array (começando do primeiro elemento). Se um elemento for 0, não será possível mover-se por esse elemento.

Exemplo:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)

O primeiro elemento é 1, então só pode ir para 3. O segundo elemento é 3, então pode fazer no máximo 3 etapas, por exemplo, para 5, 8 ou 9.

<?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 INT_MAX;
      
    // 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, 6, 3, 2, 3, 6, 8, 9, 5);
$n = count($arr);
  
echo "Minimum number of jumps to reach "
     . "end is ". minJumps($arr, 0, $n-1);
      
// This code is contributed by Sam007
?>

<?php
// PHP code for Minimum number of
// jumps to reach end
  
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
function minJumps($arr, $n)
{
    // jumps[n-1] will
    // hold the result
    $jumps = array($n);
      
    if ($n == 0 || $arr[0] == 0)
        return 999999;
  
    $jumps[0] = 0;
  
    // Find the minimum number of
    // jumps to reach arr[i]
    // from arr[0], and assign 
    // this value to jumps[i]
    for ($i = 1; $i < $n; $i++)
    {
        $jumps[$i] = 999999;
        for ($j = 0; $j < $i; $j++)
        {
            if ($i <= $j + $arr[$j] && 
                $jumps[$j] != 999999)
            {
                $jumps[$i] = min($jumps[$i], 
                             $jumps[$j] + 1);
                break;
            }
        }
    }
    return $jumps[$n-1];
}
  
    // Driver Code
    $arr = array(1, 3, 6, 1, 0, 9);
    $size = count($arr);
    echo "Minimum number of jumps to reach end is ". 
                             minJumps($arr, $size);
                               
// This code is contributed by Sam007
?>

Artigo contribuído por:

GeeksforGeeks

Vote na dificuldade

<button class="btn" data-gfg-action="article-difficulty" data-rating="1">Fácil</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="2">Normal</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="3">Médio</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="4">Duro</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="5">Especialista</button>

Tags de artigo:

• Programas PHP

Reportar problema