python - Dynamic programming doesn't give correct answer -

i found out technique called dynamic programming , stumbled upon problem can't figure out. given list of arguments in beginning , need sums on if cutting it. if list has 1 element, don't sum it. if has more, sum elements , cut in every possible way. if list has n elements, there n-1 ways cut it. picture explain:

i first wanted sum of sumable parts , expected result 20( 11 + 9 ) ( thought correct answer 9 ), thought start. code returns number 37 , have no idea why. doing wrong?

summ = 0  def opt( n ):     global summ      if len( n ) == 1:         return 0     else:         summ += sum( n )         in range( 1,len( n ) ):             summ += opt( n[ :i ] ) + opt( n[ i: ] )          return summ  print( opt( [ 1,2,3 ] ) ) 

thank time , answer!

i think want:

def opt(n):     if len(n) == 1:         return 0     else:         return sum(n) + min(opt(n[:i]) + opt(n[i:])                             in range(1, len(n))) 

example:

>>> opt([1]) 0 >>> opt([1, 2]) 3 >>> opt([2, 3]) 5 >>> opt([1, 2, 3]) 9 >>> opt([1, 2, 3, 4]) 19 

dynamic programming dividing "big problem" small subproblems.

so, first of all, should identify how big problem related subproblems. writing recurrence relation. in case:

opt(nums) = sum(nums) + min(...) 

you need starting point:

opt(nums) = 0 iff len(nums) == 1 

as can see, once have wrote recurrence relation, transforming python code straightforward.

it's important understand each subproblem self-contained, , should not need external input. use of global variables not producing wrong result, against spirit of dynamic programming.

your use of trees expressing opt() nice. forgot writing relationship between each node , children. if did, i'm sure have found correct solution yourself.

we not finished yet (thanks stefan pochmann noticing). in order build true dynamic programming solution, need avoid solving same problem more once. currently, running opt([1,2,3,4]) results in calling opt([1,2]) more once. 1 way prevent using memoization:

cache = {}  def opt(n):     # tuple objects hashable , can put in cache.     n = tuple(n)      if n in cache:         return cache[n]      if len(n) == 1:         result = 0     else:         result = sum(n) + min(opt(n[:i]) + opt(n[i:])                               in range(1, len(n)))      cache[n] = result     return result 

by way, remember handle case n empty (i.e. len(n) == 0).