Minimum cumulative sum when combining adjacent elements

[iamnone12]

'N' positive integers are placed in a circle in such a way such that for each valid i, A(i) and A(i+1) are adjacent, and A(1) and A(N) are also adjacent.

We want to repeat the following operation exactly N−1 times (until only one number remains): :-)

1)Select two adjacent numbers. Let's denote them by a and b.

2)Score a+b points.

3)Erase both a and b from the circle and insert a+b in the space between them.

What is the minimum number of points we can score ?

Example:-

[10 10 1]

[10,10,1]→[10,11] , Score: 11

[10,11]→[21], Score: 21

Total Score: 11+21 = 32

How can I solve this problem using dynamic programming ?

My approach is to brute-force and try all possible ways.

[aryaaa5]

try greedy method and figure it out yourself :)

[abo]

U have to select the pair with minimum sum with updations . So its better to compute the minimum adjacent sum and update it after doing step no 2.

example :
5
7 3 4 1 5

Solution :

7 3 (4+1) 5 // Sum = 5
7 3 5 5
7 (3+5) 5 // Sum = 5+ 8=13
7 8 5
8 (7+5) // Sum = 13+12=25
(Addition of 7,5 is possible because it is circular array)
8 12
(8+12) // Sum = 25 +20=45
Final answer = 45.
Hope this helps.

[bazingapunk]

greedy approach is not working

[keskiverto]

Deja vu: http://www.cplusplus.com/forum/beginner/256890/

MikeyBoy wrote:

If this is a Codechef problem, you should know that the Codechef adjudicators are aware of this forum, and that people use it to cheat on their contests. If you use this forum to try and cheat, you run the risk of being disqualified.