Finding the minumum intermediate sum

[jupa86]

Hi everyone!

I need some help to find a recurrence formula to the next problem.

I have a sequence of positive numbers of size N and I need to distribute N-1 parentheses in the sum of these positive integers. For example if I have the sequence (for N=4) 4,1,2,3 then a posible distribution is:
((4+1)+(2+3)) and other is (4+((1+2)+3)) but the objetive of this probles is using Dynamic Programming find the minumum sum of the intermediate sums ie in the first example (4+1)=5 (one of the intermediate sums) (2+3) = 5 (the second) and the third (5+5)=10 then the sum in this case is 5+5+10 = 20 and for the second case the sum is 3 + 6 + 10 = 19.

I hope someone could understand my explanation and help me.

Thank's

[ProgramArtist]

I hope someone could understand my explanation and help me.

Sorry, I don't understand your problem. In a sum of N integers you can set as many parantheses you want, the result will be always the same. Of course the sums inside your parantheses could be different.

and for the second case the sum is 3 + 6 + 10 = 19.

Can you explan how you got this "3 + 6 + 10"? I didn't get the point here.

With regards
Programartist

[nuzzle]

Sorry, I don't understand your problem. In a sum of N integers you can set as many parantheses you want, the result will be always the same.


Sure, the sum will be the same but not the sum of all intermediate sums. Say you have

1+2+3

The sum will always be 6 but the sum of the intermediate sums will differ depending on whether you sum like this

(1+2)+3

or like this

1+(2+3)

In the first case the first intermediate sum is 1+2=3 and the second is 3+3=6. The sum of these sums is 9.

In the second case the first intermediate sum is 2+3=5 and the second is 1+5=6. The sum of these sums is 11.