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:
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 |