Listing the total sum of all possible sums in a set with constraints

Question

I am keen to find out the following:

Given a set with N elements, my friend and I are playing a game.I always make the first move. We can only remove either the first or the last element with 50% chance each.We take alternate turns in the game.If only one element remains,we can remove it for sure.What is the expected sum that I can collect?

For example:N=2 {10,20} Possible sets that I can collect are {10},{20}.
So expected sum is 0.5*10+0.5*20=15.

My approach:

Since probability of getting a possible sum is equal in all cases,we only need to compute the sum of all possible sums and then multiply it by (0.5)^N/2.

I tried to use recursion to compute the required sum:

f(i,j)-computes the sum between i and j recursively
f(i,j)=2*a[i]+func(i,j-2)+func(i+1,j-1)+func(i+1,j-1)+func(i+2,j)+2*a[j]);
Initial call f(1,N)

But the approach doesn't seem to work. What should I do?

Complete function is below:

class CandidateCode {
    static long v[][] = new long[1003][1003];

    public static long func(int a[], int i, int j) {
        if (i == j)
            return v[i][j] = a[i];
        if (v[i][j] != 0)
            return v[i][j];
        else {
            if (i > j - 2 && i + 1 > j - 1 && i + 2 > j)
                return (v[i][j] += 2 * a[i] + 2 * a[j]);
            else
                return (v[i][j] += 2 * a[i] + func(a, i, j - 2) + func(a, i + 1, j - 1) + func(a, i + 1, j - 1)
                        + func(a, i + 2, j) + 2 * a[j]);
        }
    }

    public static void main(String args[]) {
        int n;
        int a[] = { 0, 6, 4, 2, 8 };
        n = a.length - 1;
        System.out.println(func(a, 1, 4) / Math.pow(2, n / 2));
    }
}

Answer 1

This problem can be solved by applying dynamic programming.

First, we have the state of the game is (player ,start, end) ,which indicates the current player, and the range of values that's available in the original set. At the beginning, we start at player 0 and start is 0, end is N - 1.

Denote that the first player is 0 and the second player is 1, we have the expected value of player 0:

 if(player == 0){
    double result = 0.5*( set[start] + f(1, start + 1,end) ) + 0.5*(set[end] + f(1,start, end - 1));
 }else{
     double result = 0.5*( f(0, start + 1,end) ) + 0.5*(f(0,start, end - 1));
 }

So for each state, we can store all calculated state in a dp[player][start][end] table, which reduce the time complexity to O(2*N*N) with N is number of value in set.

Pseudo code:

 double expectedValue(int player, int start, int end, int[]set){
       if(start == end)
          if(player == 0)
             return set[start];
          return 0;
       if(already calculated this state)
          return dp[player][start][end];
       double result= 0;
       if(player == 0){
          result = 0.5*( set[start] + f(1, start + 1,end) ) + 0.5*(set[end] + f(1,start, end - 1));
       }else{
          result = 0.5*( f(0, start + 1,end) ) + 0.5*(f(0,start, end - 1));
       }
       return dp[player][start][end] = result;
  }