SRM 656 Div1 Easy RandomPancakeStack

dp(i,j):i番目の操作でj番目のパンケーキを置く確率

class RandomPancakeStack {
public:

int N;
double memo[300][300];

double dp(int i,int j){
    if(memo[i][j]>1e-9) return memo[i][j];
    if(i==0) return memo[i][j]=1.0/N;
    double res=0;
    for(int k=j+1;k<N;k++) res+=dp(i-1,k)/(N-i);
    return memo[i][j]=res;
}

double expectedDeliciousness(vector <int> d) {
	N=d.size();
    REP(i,300)REP(j,300) memo[i][j]=0;
    double res=0;
    REP(i,N)REP(j,N) res+=dp(i,j)*d[j];
    return res;
}