Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: problem while solving basic dynamic programming question

by haukex (Chancellor)
on Mar 15, 2020 at 08:42 UTC ( #11114285=note: print w/replies, xml ) Need Help??


in reply to problem while solving basic dynamic programming question

if(defined $cache[$num]) {return $cache[$num];} if($num < 0) {return 0;}

In Perl, -1 is a valid array index, meaning the last element of the array (-2 is the second-to-last, and so on). Move the if($num < 0) check before the if(defined $cache[$num]) check and your code produces the expected output. Another option would be to use a hash instead of an array as the cache.

A couple more tips:

  • Instead of a global, you could define your cache as what is known as a "static" variable in other languages, using state.
  • Update: While implementing the cache yourself like that is fine, note that Perl has a module for that, Memoize.
  • The &find() style of calling subs is outdated, call your subs without the &.
  • The if($num == 0) check isn't necessary if you pre-populate your array with that index.
  • You can use Test::More instead of inputting your test cases manually:
use warnings; use strict; use feature 'state'; sub find { state @cache = (1); my $num = shift; return 0 if $num < 0; if ( defined $cache[$num] ) { return $cache[$num] } $cache[$num] = find($num-1) + find($num-2) + find($num-3); return $cache[$num]; } use Test::More tests=>3; is find(2), 2; is find(3), 4; is find(4), 7;

Replies are listed 'Best First'.
Re^2: problem while solving basic dynamic programming question
by yujong_lee (Novice) on Mar 22, 2020 at 05:56 UTC
    It was helpful. Thank you

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11114285]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2020-05-31 16:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If programming languages were movie genres, Perl would be:















    Results (175 votes). Check out past polls.

    Notices?