Existem n escadas, uma pessoa que está na parte inferior quer chegar ao topo. A pessoa pode subir 1 ou 2 degraus de cada vez. Conte o número de maneiras pelas quais a pessoa pode chegar ao topo.
 

Considere o exemplo mostrado no diagrama. O valor de n é 3. Existem 3 maneiras de chegar ao topo. O diagrama é retirado dos quebra-cabeças de Fibonacci mais fáceis 
 

<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb 1, 2, ..m stairs
// at a time.
 
// A simple recursive
// function to find n'th
// fibonacci number
function fib($n)
{
if ($n <= 1)
    return $n;
return fib($n - 1) +
       fib($n - 2);
}
 
// Returns number of
// ways to reach s'th stair
function countWays($s)
{
    return fib($s + 1);
}
 
// Driver Code
$s = 4;
echo "Number of ways = ",
           countWays($s);
 
// This code is contributed
// by m_kit
?>

Número de maneiras = 5

A complexidade de tempo da implementação acima é exponencial (proporção áurea elevada à potência n). Ele pode ser otimizado para trabalhar em tempo O (Logn) usando as otimizações de função de Fibonacci discutidas anteriormente . 
 

<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb either 1 or 2
// stairs at a time
 
// A recursive function
// used by countWays
function countWaysUtil($n, $m)
{
    if ($n <= 1)
        return $n;
    $res = 0;
    for ($i = 1; $i <= $m &&
                 $i <= $n; $i++)
        $res += countWaysUtil($n - $i, $m);
    return $res;
}
 
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
    return countWaysUtil($s + 1, $m);
}
 
// Driver Code
$s = 4; $m = 2;
echo "Number of ways = ",
      countWays($s, $m);
     
// This code is contributed
// by akt_mit
?>

Número de maneiras = 5

<?php
// A PHP program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
 
// A recursive function used by countWays
function countWaysUtil($n, $m)
{
    $res[0] = 1; $res[1] = 1;
    for ($i = 2; $i < $n; $i++)
    {
        $res[$i] = 0;
        for ($j = 1; $j <= $m && $j <= $i; $j++)
        $res[$i] += $res[$i - $j];
    }
    return $res[$n - 1];
}
 
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
    return countWaysUtil($s + 1, $m);
}
 
    // Driver Code
    $s = 4;
    $m = 2;
    echo "Number of ways = ", countWays($s, $m);
 
// This code is contributed by m_kit
?>

 de maneiras = 5

Consulte o artigo completo sobre Contagem de maneiras de chegar à enésima escada para obter mais detalhes!