Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: problem while solving basic dynamic programming question

by vr (Curate)
on Mar 15, 2020 at 11:11 UTC ( #11114287=note: print w/replies, xml ) Need Help??


in reply to problem while solving basic dynamic programming question

Ehm... If you accept 3 in list of answers for input "3", then there should be 4 in list for "4", then total count for the latter would be 8, not 7. In fact, said count is equal 2**(N-1), rather than Tribonacci sequence with whatever initial triplet as your code implies.

Visualize it this way: there are N ones 1,1,1,.... You insert any number of pluses in between and perform these additions to get partial answer. So, emit all subsets of all positions, it should be clear enough. I'd NOT recommend to submit code below if this is HW assignment. Result is correct, algo is kind of joke.

use strict; use warnings; use Algorithm::Combinatorics 'subsets'; $" = ' + '; use constant N => 5; my $i = subsets [ 1 .. N - 1 ]; while () { my $s = '1,' x N; substr $s, 2 * $_ - 1, 1, '+' for @{ $i-> next or last }; print eval( $s = "@{[ eval $s ]}" ), " = $s\n"; } __END__ 5 = 5 5 = 1 + 4 5 = 2 + 3 5 = 1 + 1 + 3 5 = 3 + 2 5 = 1 + 2 + 2 5 = 2 + 1 + 2 5 = 1 + 1 + 1 + 2 5 = 4 + 1 5 = 1 + 3 + 1 5 = 2 + 2 + 1 5 = 1 + 1 + 2 + 1 5 = 3 + 1 + 1 5 = 1 + 2 + 1 + 1 5 = 2 + 1 + 1 + 1 5 = 1 + 1 + 1 + 1 + 1

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (7)
As of 2020-06-01 06:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?