How to choose n/2 (n is even) elements from the array such that their sum is minimum and no two elements are adjacent to each other: [4, 2, 1, 1] 1 + 2 = 3 [3, 3, 3, 0, 4, 0] 3 + 0 + 0 = 3 [2, 0, 11, 2, 0, 2] 0 + 2 + 2 = 4

can we do it greedy? (no dp pls)

we must choose n/2 element so choose index 1,3,5 or 2,4,6 in case of lenght six and minimum of both is answer.

1 4 6, 1 3 6?

oh then i know only 1 way dp

You have to choose all odd indexes or all even indexes so just test the sum of these two and see which one is minimum.

but choosing from both odd/even indexes maybe optimal: 1,3,6 etc.

Then you can't take n/2 element.

we must take n/2 elements with min sum, pls reread the description

Initialize 2 prev elements

`(podd=0,peven=0)`

and 2 cur elements`(codd=0,ceven=0)`

Let's say the array is 1-indexed, then:if the index is odd then:

`codd=a[i]+podd;`

if the index is even then:

`{ceven=a[i]+min(podd,peven); podd=codd; peven=ceven;}`

And Final answer will be:

`min(codd,ceven)`

This will work because we have to take n/2 elements.

[PS: Although this is just space optimized O(1) DP, but the thought process is mostly greedy and easier to understand]

thank you, will need time to digest)

Your Welcome

You just have to think along the lines:

`ceil(index/2.0)`

number of elements, not more not less because if it contains more then there will definitely be some elements before them that are adjacent, if it contains less then you can't make n/2 elements from the remaining pair.Example:Example:Example:got it for a 100% now. thank you)