________                         ________
            |        |____                   |        |____    
      ______|             |            ______|             |   
     |                    |           |                    |   
 ____|                    |  =>   ____|    subproblem      | 
|                         |      |_________________________|   
|                         |      |     a single strip      |   
|_________________________|      |_________________________|   

##</code><code>##

             ________                         ________
            |        |____                   |        |____    
      ______|             |            ______|             |   
     |                    |           |      |             |   
 ____|                    |  =>   ____|      |             | 
|                         |      |           | subproblem  |   
|                         |      | subproblem|             |   
|_________________________|      |___________|_____________|   

##</code><code>##

             ________                            ________
            |        |____                      |________|____    
      ______|             |               ______|             |   
     |                    |  NEVER!      |______|_____________|   
 ____|                    |    =>    ____|____________________| 
|                         |         |___________|             |   
|                         |         |           |_____________|   
|_________________________|         |___________|_____________|   

##</code><code>##

use List::Util qw(min sum);
use strict;
use Memoize;

memoize 'solve';

my @thicknesses = (4, 8, 16, 24, 32, 47, 64);
my @goal = ( [10,20], [15,28], [20,48], [10,40] );

sub argmin(&@) {
    my $i = undef;
    my $min = undef;
    my $block = shift;
    for (@_) {
         my $this = $block->($_);
         if ( not defined $min or $min > $this ) {
             $min = $this;
             $i = $_;
         }
    }
    return wantarray ? ($i, $min) : $i;
}

my @decomp;
my $INFINITY = 1e10;

sub solve {
    my ($left, $right, $height) = @_;

    ## we could either we can split into two pyramids..

    my ($split_index, $split_value) = (undef, $INFINITY);
    if ($left != $right) {
        ($split_index, $split_value) =
            argmin { solve($left, $_, $height)
                      + solve($_+1, $right, $height) } $left .. $right-1;
    }


    ## ... OR we could try to place a strip across the whole length

    my $min_height = min map { $_->[1] - $height } @goal[$left .. $right];
    my @strips = grep { $_ <= $min_height } @thicknesses;

    ## (degenerate case, nothing left to do!)
    return 0 if $min_height == 0 and $left == $right;

    my ($strip_size, $strip_value) = (undef, $INFINITY);
    if (@strips) {
        ($strip_size, $strip_value) =
            argmin { 1 + solve($left, $right, $height+$_) } @strips;
    }

    ## which one of these is best?

    if ($strip_value < $split_value) {
        $decomp[$left][$right][$height] =
            [ strip => sum( map { $goal[$_][0] } $left .. $right ),
                       $strip_size ];
        return $strip_value;
    } else {
        $decomp[$left][$right][$height] = [ split => $split_index ];
        return $split_value;
    }
}   

printf "you can solve this with %d strips\n",
    solve(0, $#goal, 0);

reconstruct(0, $#goal, 0);

sub reconstruct {
    my ($left, $right, $height) = @_;
    my $how = $decomp[$left][$right][$height];

    return if not ref $how;
    if ($how->[0] eq "strip") {
        print "strip of length $how->[1], height $how->[2]\n";
        reconstruct($left, $right, $height + $how->[2]);
    } else {
        my $split = $how->[1];
        reconstruct($left, $split, $height);
        reconstruct($split+1, $right, $height);
    }
}

##</code><code>##

you can solve this with 5 strips
strip of length 55, height 16
strip of length 25, height 4
strip of length 15, height 8
strip of length 20, height 32
strip of length 10, height 24