For problem I_coin of Atcoder DP contest,
I_coin:problem link
I wrote a recursive DP approach , but my solution is getting passed only in 14 test cases out of 33, i wrote a very simple solution and commented as well. Any help i debugging my code is appreciated.
my submission atcoder:https://atcoder.jp/contests/dp/submissions/21056478
please help @tamo11 @ssjgz @infinite_king @spaanse @peresz @therealnishuz
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int N;
float P[3002]; //Probability array
vector<vector<double>> dp(3002, vector<double>(3002,-1)); //DP TABLE
double f_prob=0;
double fun(int N,int K){ //function corresponding to dp where N is Nth coin state and K heads are required
if(N==0){ if(K>0){ return 0;}else{ return 1;} }
if(dp[N][K]!=-1){ return dp[N][K];}
double prob= P[N]*fun(N-1,K-1)+(1-P[N])*fun(N-1,K);
dp[N][K]=prob;
return prob;
}
int main(){
fastio;
cin>>N;
for(int i=1;i<N+1;i++){ cin>>P[i]; }
dp[1][0]=(1-P[1]);
for(int i=2;i<=N;i++){
dp[i][0]=(1-P[i])*dp[i-1][0];
}
dp[1][1]=P[1];
dp[0][1]=0;
for(int i=2;i<=N;i++){
dp[i][i]=P[i]*dp[i-1][i-1];
dp[0][i]=0;
}
for(int i=N;i>(N/2);i--){ double tmp=fun(N,i); f_prob+=tmp; }
cout<<setprecision(20)<<f_prob<<"\n";
return 0;}
