Classical Round Table algorithm?

Posted by user1795954 on Stack Overflow See other posts from Stack Overflow or by user1795954
Published on 2012-11-07T16:58:26Z Indexed on 2012/11/07 17:00 UTC
Read the original article Hit count: 381

Filed under:

Coins with different value are spread in circle around a round table . We can choose any coin such that for any two adjacent pair of coins , atleast one must be selected (both maybe selected too) . In such condition we have to find minimum possible value of coins selected .

I have to respect time complexity so instead of using naive recursive bruteforce , i tried doing it using dynamic programming . But i get Wrong Answer - my algorithm is incorrect .

If someone could suggest an algorithm to do it dynamically , i could code myself in c++ . Also maximum number of coins is 10^6 , so i think O(n) solution exists .

© Stack Overflow or respective owner

Related posts about algorithm