Algorithms – Domino Solitaire Algorithm

In principle, any multi-stage optimization problem is solvable using dynamic programming, if you can come up with the right notion of the state. You do not mention which class of problems you are working on, so it hard to give general guidelines. I'll make the following assumptions here:

• You are looking at deterministic optimization problems (as opposed to stochastic optimization problems).
• You have to choose finite number of decisions, and in the end want to maximize rewards that depend on all your decisions (the argument also works if you are interested in minimizing costs).
• You can decompose the total reward into sum of individual rewards, ideally, in such a way that decision n influences the total reward for the first time only from the n-th term onwards.

In order to solve such a problem by dynamic programming, you need to come up with a state state_n that satisfies the following properties:

state_n+1 = function(state_n, decision_n)

and

reward_n = function(state_n, decision_n)

If these conditions are satisfied, then dynamic programming gives an optimal solution. First you define value functions

V_n(state_n) = max_decisionn[ reward_n + V_n+1(state_n+1)]

and recursively solve for these value functions in a backward manner.

NOTE: These are the simplest class of problems that can be solved using dynamic programming. For more details, see any standard book on dynamic programming, e.g., Berksekas.

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]);
 }