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
    It was helpful. Thank you