project-euler / project-euler / 31.pl

#!/usr/bin/perl 

use strict;
use warnings;

my @coins = (1,2,5,10,20,50,100,200);

my @r_coins = (reverse(@coins));

my %cache = ();

sub calc
{
    my ($max_idx, $sum) = @_;

    if (exists($cache{"$max_idx,$sum"}))
    {
        return $cache{"$max_idx,$sum"}
    }
    else
    {
        my $ret;
        if ($max_idx == $#r_coins)
        {
            $ret = 1;
        }
        elsif ($sum < $r_coins[$max_idx])
        {
            $ret = calc($max_idx+1, $sum);
        }
        else
        {
            $ret = calc($max_idx+1, $sum)+calc($max_idx, $sum-$r_coins[$max_idx]);
        }
        return $cache{"$max_idx,$sum"} = $ret;
    }
}

print calc(0, 200), "\n";
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.