数字三角形

 

数字三角形 

问题描述 
7 

3 8 

8 1 0 

2 7 4 4 

4 5 2 6 5 


上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路
径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求
出最佳路径上的数字之和。


注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

my @result;
my @data =(
    [1],
    [2,3],
    [4,5,6],
    [7,8,9,10],
    [14,3,6,8,6]
);

#the path value to the first element is 1
$result[0][0] = $data[0][0];

sub MaxSingleStep{

    #now get the path with max value to $data[$level][$tarI]
    my $tarI = shift;
    my $level = shift;


    #get the possible element which can reach [$level][$tarI]
    my $si = $tarI - 1 ;
    my $ei = $tarI +1;
    if($si < 0){
        $si = 0;
    }


    #select the element with max path value
    my $pathv = 0;
    for($si..$ei){
        if($pathv < $result[$level-1][$_] and defined($result[$level-1][$_])){
            $pathv = $result[$level-1][$_];
        }
    }

    #the path value is the sum of selected element path value the current element
    $result[$level][$tarI] = $pathv + $data[$level][$tarI];
}




#go through all element by level
for my $level (1..4){
    #go through element in every level
    for my $index (0..$level){
        MaxSingleStep($index,$level);
    }
}

#output
my $max = 0;
for(@result[@data-1]){
    for(@{$_}){
        $max = $_ if($max<$_);
    }
}
print $max;