• it calculates best cost and path for both test cases.
• for one "pathological" triangle with 100 rows with all cells 1
• for one "random" triangle with 100 rows and random entries

Our approaches are not that different, your dynamic "cache" is just my explicit "weight" triangle.

And you are needing more resources for recursion and hash.

But you could improve it by adding bound criteria (i.e. no need to calculate a subtree if it has no chance to be better than the current minimum).

edit

Though I'm not sure this will pay of, my algorithm is already O(m) with m #cells.

For people who don't like recursion and hashes :)

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11128406
use warnings;
use List::Util qw( reduce );

local $_ = <<END;
            1
           2 4
          6 4 9
         5 1 7 2
END
my @d = map [ split ], split /\n/;

for my $r ( reverse 0 .. $#d - 1 )
  {
  for my $c ( 0 .. $r )
    {
    $d[$r][$c] .= ' + ' . reduce { eval $a <= eval $b ? $a : $b }
      $d[$r+1][$c], $d[$r+1][$c+1];
    }
  }

print "$d[0][0]\n";
[download]

Or for a big mess, compute the score and the path simultaneously :)

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11128406
use warnings;
use List::Util qw( reduce min );

local $_ = <<END;
            1
           2 4
          6 4 9
         5 1 7 2
END
my @d = map [ split ], split /\n/;

$d[$#d][$_] = [ $d[$#d][$_], $d[$#d][$_] ] for 0 .. $#d;

for my $r ( reverse 0 .. $#d - 1 )
  {
  for my $c ( 0 .. $r )
    {
    $d[$r][$c] = [ $d[$r][$c] + min( $d[$r+1][$c][0], $d[$r+1][$c+1][0
+]),
      "$d[$r][$c] + " . (reduce { $a->[0] <= $b->[0] ? $a : $b }
      $d[$r+1][$c], $d[$r+1][$c+1])->[1] ];
    }
  }

print "value $d[0][0][0]  path $d[0][0][1]\n";
[download]

Outputs:

value 8  path 1 + 2 + 4 + 1
[download]