I dont understand the usage of c and f in your code. It would be great if you could explain a bit on that. Also i dont find the need to iterate i-2 and i-1 for every i. ( I am not able to comment on posts yet) Now i ll give you my algorithm to solve this problem similar to your approach.

Maintain a dp[n][2]. dp[i][0] is for cases starting from 0 and dp[i][1] for the ones starting from 1. Now for each i, you could just get the dp[i][0]th element as dp[i-2][0] + k[i] and dp[i][1] as dp[i-2][1] + k[i]. Trick is to do this only when appropriate. Here for cases where i%2 is equals 0, you can assume that those are the ones that will be covered when we start from 0 and rest of elements goes for the other case. Corner case will be to avoid the last element for the case of starting from 0 as the table is circular.

Here is my working code. It works for the case you just mentioned. Am not a member of the site so am not able to test for other cases though.

#include<vector>
#include<iostream>
#include<cmath>
using namespace std;

int main() {
int n, i, j, temp;
vector<int> k;
cin>>n;
for(i=0;i<n;i++) {
cin>>temp;
k.push_back(temp);
}
int dp[n][2];
/* 0 will contain the case of starting from 0
* 1 will contain the case of starting from 1 */
dp[0][0] = k[0];
dp[0][1] = 0;
dp[1][0] = k[0]; // assign the previous value itself 
dp[1][1] = k[1];

for(i=2;i<n;i++) {      
    if(i%2 == 0) {
        // case of strting from 0 . 


        dp[i][0] = dp[i-2][0] + k[i];
        dp[i][1] = dp[i-1][1];              
    }
    else{ // case of starting from 1
        dp[i][0] = dp[i-1][0];
        dp[i][1] = dp[i-2][1] + k[i];           
    }       
}
cout<<min(dp[n-1][0], dp[n-1][1]);
 }

So I’ve looked at your code, and I have to be honest, it will take me quite a bit longer to get into your frame of mind and code then I’m willing to put in. But I can suggest an alternative way of dividing the sub problems that I think will be easier to understand and write.

Define a 4x(n+1) array. At index i,j the j index corresponds to the sub-problem of the first n knights. The last spot is the first one repeated again. The 4 array locations correspond to 4 different cases, corresponding to whether or not the very first knight got his dessert, and whether the jth knight got his dessert.

The base case is easy to do because we have restricted whether or not the first knight gets dessert. So it’s even more trivial than usual. To solve the current case in terms of previous cases is fairly straightforward: the cases where the first knight does or doesn’t get dessert are completely separate. For each case, the value for the case where the current knight gets dessert is the min of the previous entries, plus the current cost of dessert. The case where he doesn’t is the sum of the previous solution where the last knight did get dessert, plus the current cost of dessert.

To wrap up the algorithm: out of the 4 rows, only 2 are relevant, because only 2 correspond to cases where the beginning and end (which is the beginning repeated) are consistent. Take the smallest out of these two.

I think your algorithm does not work because the table is circular. But we can solve this using a different dynamic programming approach.

Let array ‘C[]’ store the costs of the desserts of each knights. We have to consider two things:

1. W[i], The cost of including the ith knight
2. _W[i], The cost of not including the ith knight, in this case we have to include its neighbours.

Let us forget about the table being circular for a while. As we are moving forward in each iteration _W[i] stores only the cost of including the left neighbour of ‘i’.

For a particular knight ‘k’, we can compute W[k] and _W[k] in constant time by using the already computed values of W[k-1] and _W[k-1].

If we dont include knight ‘k’, we have to include knight ‘k-1’ so that at least one of them gets his dessert. Therefore _W[k] will be equal to the cost of including knight ‘k-1’, which is W[k-1].

If we choose to include knight ‘k’, we have two choices, either include ‘k’ and ‘k-1’ both, or include ‘k’ and not ‘k-1’. We take the minimum of the two.

Now we have:

• _W[k] = W[k-1]
• W[k] = C[k] + min(W[k-1],_W[k-1])

So, if we know the value of _W[0] and W[0] then we can compute the W, and _W values for all knights upto N.

We know W[0] will be equal to C[0]. _W[0], the cost of not including knight 0, will be the cost of including its left neighbour which, if we come back to the original problem is C[N-1].

But what will happen if W[1] is chosen as _W[0] + C[1] where _W[0] is C[N-1]? We might consider knight N-1 twice.

To overcome this problem we check if C[N-1] < C[0], if it is then we know that knight N-1 will be chosen so we decrease N by one and therefore delete the last knight.

The final answer will be the minimum of W[N-1] and _W[N-1]

If you need the pseudocode:

 W[0] = C[0]
_W[0] = C[N-1]

   if C[N-1] < C[0]:
         then N = N-1

   for i from 1 to N-1:
       W[i] = C[i] + min(W[i-1],_W[i-1])
       _W[i] = W[i-1]


   return min(W[N-1],_W[N-1])

As you do constant amount of time in each iteration the time complexity is O(N), which will run well within the time limits of your problem.