Classical Round Table algorithm?
- by user1795954
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 .