I'm solving basic dynamic programming question.
It's simple. input is single integer. if input is 3, all possible cases is 3,1+2,2+1,1+1+1 so out put is 4.
if input is 4, output is 7 because
4 = 1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1.
code above is my code to solve this.

`use strict;
use warnings;
our @cache;
sub find {
my $num = shift;
if(defined $cache[$num]) {return $cache[$num];}
if($num == 0) {return 1;}
if($num < 0) {return 0;}
$cache[$num] = &find($num -1) + &find($num - 2) + &find($num - 3);
return $cache[$num];
}
my $test_case = <>+0;
for(1..$test_case) {
my $num = <>+0;
print &find($num),"\n";
}
`

but the output is wrong. and I found that output of 2 is 3, instead of 2. also output of 3 is 5 instead of 4.
to fix this, I write @cache1..3 = (1,2,4); and of course, It is fixed.
But, I want to remove @cache1..3 = (1,2,4); and want to know why my original code is not working properly.
when call solution(2), isn't it obvious that the output is solution(1) + solution(0) + solution(-1)?
and when I call solution(0), solution(1), solution(-1) individually, the output is 1,1,0 so sum is 2. not 3.
Thank you for your help.

Comment onproblem while solving basic dynamic programming questionDownloadCode