Efficient implementation of a Dynamic Programming challenge
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.