TheTask1337 TheTask1337 - 2 years ago 145
Python Question

Dynamic programming doesn't give correct answer

I recently found out about the technique called dynamic programming and I stumbled upon a problem which I can't figure out. You are given a list of arguments in the beginning and you need to do sums on as if you were cutting it. If the list has only one element, you don't sum it. If it has more, you sum the elements and cut it in every possible way. So if list has n elements, there are just n-1 ways to cut it. The picture will explain:

Opt

I first wanted to sum up all of the sumable parts and I expected the result 20( 11 + 9 ) ( even thought the correct answer is 9 ), but I thought it would be a good start. But my code returns number 37 and I have no idea why. What am I doing wrong?

summ = 0

def Opt( n ):
global summ

if len( n ) == 1:
return 0
else:
summ += sum( n )
for i in range( 1,len( n ) ):
summ += Opt( n[ :i ] ) + Opt( n[ i: ] )

return summ

print( Opt( [ 1,2,3 ] ) )


Thank you for your time and any answer!

Answer Source

I think this is what you want:

def Opt(n):
    if len(n) == 1:
        return 0
    else:
        return sum(n) + min(Opt(n[:i]) + Opt(n[i:])
                            for 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 is about dividing the "big problem" into small subproblems.

So, first of all, you should identify how the big problem is related to the subproblems. You do this by writing a recurrence relation. In this case:

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

You also need a starting point:

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

As you can see, once you have wrote the recurrence relation, transforming it into Python code is often straightforward.

It's important to understand that each subproblem is self-contained, and should not need external input. Your use of global variables is not only producing the wrong result, but it's against the spirit of dynamic programming.

Your use of trees for expressing Opt() is nice. What you forgot to do is writing the relationship between each node and its children. If you did, I'm almost sure that you would have found the correct solution yourself.

By the way, remember to handle the case where n is empty (i.e. len(n) == 0).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download