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
- The input starts with two integers
- Output
- You should output the probability (
) of the season beeing successful
- You should output the probability (
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

What we need is the probability of at least

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
)
- The cache is of size
- 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 upfor 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