title: Dynamic Programming and Probability
body: <p>I've been staring at this problem for hours and I'm still as lost as I was at the beginning. It's been a while since I took discrete math or statistics so I tried watching some videos on youtube, but I couldn't find anything that would help me solve the problem in less than what seems to be exponential time. Any tips on how to approach the problem below would be very much appreciated!</p>
  
  <blockquote>
    <p>A certain species of fern thrives in lush rainy regions, where it typically rains almost every day.
    However, a drought is expected over the next n days, and a team of botanists is concerned about
    the survival of the species through the drought. Specifically, the team is convinced of the following
    hypothesis: the fern population will survive if and only if it rains on at least n/2 days during the
    n-day drought. In other words, for the species to survive there must be at least as many rainy days
    as non-rainy days.
    Local weather experts predict that the probability that it rains on a day i ∈ {1, . . . , n} is
    p<sub>i</sub> ∈ [0, 1], and that these n random events are independent. Assuming both the botanists and
    weather experts are correct, show how to compute the probability that the ferns survive the drought.
    Your algorithm should run in time O(n<sup>2</sup>).</p>
  </blockquote>