Efficient implementation of a Dynamic Programming challenge

I wrote the following code for a Dynamic Programming problem but the online judge gives me a 'Time Limit Exceeded' error. How can I optimize this code to make it more efficient, especially the part of initializing the DP array to 0.0 (I am using memset() right now)?

Problem:

• There are N values in an array. Two players take turn by turn to play the game.

• Player1, with 50% probability can pick the left most value or the right most value.

3.If there is only one value left in the array, the player, having no more choice, will just pick up that value.

• Question is to calculate the expected sum of values that First player can obtain.

• \$T

#include
#include
#include
#include
using namespace std;
#define max  2000
int main(){
    int T;
    double **dp = new double*[max];
    for(int i=0; i> T;
    while(T--){
            int N;
            cin >> N;
            int V[N];
            for(int i=0; i> V[i] ;
            for(int i=0; i=0; --i){
                            dp[j][i] = 0.5 * ( dp[i][i] + dp[j][j] + dp[j-1][i+1] );
                            if( (i+2)=0 )
                                    dp[j][i] += (0.250 * dp[j-2][i]);
                    }
            cout << setprecision (5) << dp[N-1][0] << endl;
    }
    for(int i=0; i<max; ++i)
            delete[] dp[i];
    delete dp;
    return 0;
}

It looks like the nested loops of your algorithm are using only three rows of the dp matrix:

dp[j]
dp[j-1]
dp[j-2]

You can use this observation to transform your solution from one requiring O(N^2) space to one requiring O(N) space by changing

double **dp = new double*[max];

to

double dp[3][max]; // Now your matrix has a chance of fitting on the stack

and adding %3 to all operations that touch the first index of the dp matrix.

This may or may not eliminate the timeout, but it will make your program better by reducing the amount of resources that it needs to operate.

StackExchange Code Review Q#16111, answer score: 2