[AtCoder] I - Coins

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : I - Coins
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : Dynamic Programing 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 3000 + 5;
 
int tcoin;
double probability[maxn];
 
double dp[maxn][maxn];
bool memoize[maxn][maxn];
 
inline double solve(int pos = 0, int head = 0)
{
      if (pos >= tcoin)
      {
            int tail = tcoin - head;
            return head > tail;
      }
      double &ret = dp[pos][head];
      bool &mem = memoize[pos][head];
      if (mem) return ret;
      mem = 1;
      double sum = 0.0;
      sum += (probability[pos] * solve(pos+1, head+1) + (1 - probability[pos]) * solve(pos+1, head));
      return ret = sum;
}
 
int main()
{
      cin >> tcoin;
      for (int i = 0; i < tcoin; i++) cin >> probability[i];
      cout << setprecision(10) << solve();
}