algorithm - 动态规划和概率

Question

我已经盯着这个问题好几个小时了，但我仍然像开始时一样迷失方向。我已经有一段时间没有学习离散数学或统计学了，所以我尝试在 YouTube 上观看一些视频，但我找不到任何可以帮助我在比指数时间内解决问题的东西。任何有关如何解决以下问题的提示将不胜感激!

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_i ∈ [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²).

Answer 1

有一个(n + 1) × n矩阵使得 C[i][j]表示 i 之后的概率那天会有j雨天( i 从 1 运行到 n ， j 从 0 运行到 n )。初始化:

• C[1][0] = 1 - p[1]
• C[1][1] = p[1]
• C[1][j] = 0对于 j > 1

现在循环天数并设置矩阵的值，如下所示:

• C[i][0] = (1 - p[i]) * C[i-1][0]
• C[i][j] = (1 - p[i]) * C[i-1][j] + p[i] * C[i - 1][j - 1]对于 j > 0

最后，对 C[n][n/2] 中的值求和至C[n][n]以获得蕨类植物存活的概率。