Season-Success is an algorithmic problem that does not only deal with probabilistics but also benefits from dynamic programming. In order to fully understand what going on, you should be familiar with the fundamentals of probability and dynamic programming.

The problem goes as follows:

Assume that you are a farmer and your new years resolution was to invest in your farm. In order get a loan from the bank you have to compute the probability of a successful harvest this year. To do that you manage to get a list of days and, for each day, the probability of rain on this day . How can you compute the probability that the season is a success, which it is if there are at least rainy days among those days.

• Input
• The input starts with two integers where is the total number of days of the season and is the minimum number of days it must rain for the season to be a success.
• The next lines each contain one real number that denote the probability of rain on day
• Output
• You should output the probability () of the season beeing successful

The first step here is to understand what we have to calculate. We subsequently assume that we have already handled the input and that we have

• An integer
• An integer
• An array of probabilities

We can generalize the problem above:

Given a set of events and a function that assigns each of those events a probability of occuring, calculate the probability that at least of those events will occur.

Now let be some indicator variable that is defined as follows:

We can clearly define the random variable that denotes the number of occuring events like this

What we need is the probability of at least events occuring which is

A trivial solution would therefore be to compute by calculating all probabilities for and taking their sum. This however, can quickly become quite nasty in terms of runtime. Even if we take relatively low values like and we have

• outcomes for
• outcomes for

So going through all of them becomes extremely expensive for bigger

It should be quite intuitive that computing for some involves computing (because the probability of events occuring equals the probability of events occuring times the probability of another event occuring). This means that we have some sort of overlapping subproblems and this should ring a bell. We can use dynamic programming to significantly lessen the number of computations needed. Let’s look at how an implementation could look like:

Let be some two-dimensional DP-table that is defined as follows:

• Table structure
• The cache is of size
• stores the probability that events up to event occur (note that counting starts at )
• Computation of an entry

Explanation of the cases:
• because the probability that no events occur up to the first event is exactly the probability that the first event does not occur
• because the probability that one event occurs up to the first event is exactly the probability that the first event occurs
• because probability that no events occur up to event equals the probability that no events occur up to event times the probability of event not occuring
• because the probability that events occur up to event equals the probability that either events occur up to or that events occur up to and that does occur
• Computation order
We compute the entries of the table from left to right, top to bottom
• Retrieving the solution
By the design of our table,

So adding up for all will give us our solution

Great. Now that we know how to solve this problem using dynamic programming, lets give a java implementation. First we need a method that takes an empty table and the array of probabilities for each event, and fills the table as we have specified above

//Fills a dynamic programming table where cache[i][j] contains the probability of
//j events occuring up to event i
static double[][] fillProbCache(double[] probs, double[][] cache) {

//Base cases
cache[0][0] = 1.0 - probs[0];
cache[0][1] = probs[0];
for(int i = 1; i<cache.length; i++) {
cache[i][0] = cache[i-1][0] * (1.0 -probs[i]);
}

//Fill cache left-to-right and top-to-bottom
for(int i = 1; i<cache.length; i++) {
for(int j = 1; j<cache[0].length; j++) {
cache[i][j] = cache[i-1][j-1] * (probs[i]) + cache[i-1][j]*(1.0 - probs[i]);
}
}

return cache;
}

Now we have to instantiate the table and compute the final solution

//Given an array of length n with probabilities for n events, compute the probability that at least k of these events occur
public static double solve(double[] probs, int k) {

//Create dp-cache.
//cache[i][j] stores the probability that at least i days of snow occured
//at the first j days of the season
int n = probs.length;
double[][] cache = fillProbCache(probs, new double[n][n+1]);

//Get solution
double out = 0.0;
for(int i = k; i < n+1; i++) {
out += cache[n-1][i];
}

//output
return out;
}

And thats it.

#### Runtime

Analyzing runtime is, as with most dp-algorithms, fairly easy. Our total runtime is dominated by filling the table. Each of the table entries can be computed in constant time, so our total runtime is quadratic with