use strict;
use warnings;
use Memoize qw();

my $trans = {
    'end' => {M2    => 1},
    'M2'  => {I1    => 0.1, M1 => 0.3},
    'I1'  => {begin => 0.8},
    'M1'  => {begin => 0.2},
    };

Memoize::memoize ('viterbi');
print viterbi('end', 3);


sub viterbi {
    my ($state, $output) = @_;

    return $output == 0 ? 1 : return 0
        if $state eq 'begin';

    return 0
        if $output == 0;

    my $r = $output - 1;
    my $max;
    
    for my $yy (keys %{$trans->{$state}}) {
        my $value = $trans->{$state}->{$yy} * viterbi($yy, $r);
        
        $max = $value if ! defined $max || $value > $max;
    }
    
    return $max;
}

##</code><code>##

0.08