Solution to question 9.1 in @gayle's "Cracking the Coding Interview" 5th ed. Child/stairs/combinations-of-steps.

how-many-steps.pl

#!/usr/bin/env perl

# Solution to a question in @gayle's "Cracking the Coding Interview" 5th ed.
# A child is running up the stairs and can take 1, 2 or 3 steps at a time.
# Count how many possible ways the child can run up the stairs.
use strict;
use warnings;
use Data::Dumper;

use feature qw/ say /;

# Save on calculation time, or it's exponential-tastic
our @cache = (0);

sub perms {
  my $i = shift;
  die ("Integer out of range") if ($i < 0);

  return $cache[$i] if ( exists $cache[$i]);
  
  my $answer = 1;
 
  # You can take 1, 2 or 3 steps.
  # if you take $j steps, the number of choices afterwards
  # is the number of choices at $i - $j.
  # Simples. 
  # 'last' over 'next' is almost, almost a pointless optimisation.
  # Now imagine the choice of the number os steps you can take
  # is huge, instead of 3. Could be more important then.  
  for my $j (1, 2, 3) { 
    last if ($i < $j);
    $answer +=  perms($i - $j) 
  }
  
  # Cache it.
  $cache[$i] = $answer;
  return $answer;
}

#say perms(30);