动态规划和概率

-1

我一直在盯着这个问题好几个小时，而且我仍然像在开始时一样迷失。自从我拿出离散数学或统计数据以来，我已经有一段时间了，所以我试着在YouTube上观看一些视频，但是我找不到任何能够帮助我解决问题的东西，而这似乎不是指数级的时间。有关如何解决下面的问题的任何提示将非常感谢！动态规划和概率

某些蕨类植物在郁郁葱葱的多雨地区蓬勃发展，通常几乎每天都会下雨。然而，未来n天预计会出现干旱，植物学家团队担心物种因干旱而存活。具体而言，该团队确信以下假设：当且仅当在n天干旱期间至少n/2天下雨时，蕨类群体才能存活。换句话说，要使物种生存下来，必须至少有与下雨天一样多的下雨天数。当地天气专家预测，它在一天i∈{1，。。。，n}是 p _i∈[0,1]，并且这n个随机事件是独立的。假设植物学家和天气专家都是正确的，则展示如何计算蕨类植物在干旱中生存的可能性。您的算法应该在时间O中运行（n ）。

来源

2016-04-01 remiss

这是很简单的。递归“会下雨超过n/2天吗？”是“（今天下雨的可能性*其余日子里有2-1天会下雨的概率）+（今天没有下雨的概率*其余日子里n/2天下雨的概率）” 。显然，计算中的两个分支都有很多重叠。例如，可以设置dp矩阵，以便DP [i] [j]在剩下的j天内存储i天的降雨概率。 – aioobe

我想我已经开始掌握它了。非常感谢你！ – remiss

不客气。我还写了一个精心制作的教程式的答案，以回答另一个受欢迎的入门级DP问题[这里]（http://stackoverflow.com/a/6877313/276052），您可能会发现它具有教育意义。 – aioobe

已有(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]值来获得生存蕨的概率。

来源

2016-04-01 13:03:06 Bolo

动态规划问题可以自上而下或自下而上的方式解决。

您已经描述了自下而上的版本。要执行自上而下的版本，请编写递归函数，然后添加缓存层，以便不重新计算已经计算的任何结果。在伪代码中：

cache = {} 
function whatever(args) 
    if args not in cache 
     compute result 
     cache[args] = result 
    return cache[args]

这个过程被称为“memoization”，许多语言都有自动记忆东西的方法。

这里是一个Python实现这个具体的例子：

def prob_survival(daily_probabilities): 
    days = len(daily_probabilities) 
    days_needed = days/2 

    # An inner function to do the calculation. 
    cached_odds = {} 
    def prob_survival(day, rained): 
     if days_needed <= rained: 
      return 1.0 
     elif days <= day: 
      return 0.0 
     elif (day, rained) not in cached_odds: 
      p = daily_probabilities[day] 
      p_a = p * prob_survival(day+1, rained+1) 
      p_b = (1- p) * prob_survival(day+1, rained) 
      cached_odds[(day, rained)] = p_a + p_b 
     return cached_odds[(day, rained)] 

    return prob_survival(0, 0)

然后您可以如下调用它：

print(prob_survival([0.2, 0.4, 0.6, 0.8])

来源

2016-04-01 17:52:52 btilly

动态规划和概率

回答

相关问题