投硬币的问题

周瑜

连续投掷N次硬币，其中任意连续m次出现正面朝上次数最大值为x的概率是多少？ 如果x=m，那么就转化为N次中存在连续m次正面朝上的概率求解，本版已有答案。但是当x

KeyTo9_Fans

想到了一个动态规划算法。 记录最近$(m-1)$次抛出的正反面序列。 一共有$2^(m-1)$种序列。 记录每种序列出现的概率，空间复杂度为$O(2^m)$。 于是就可以计算再抛$1$次后，每种序列出现的概率。 一共要计算$N$次，时间复杂度为$O(N*2^m)$ 不知道有没有多项式时间复杂度的算法。

wayne

1# 周瑜 所谓的任意连续m次正面朝上，是指这个连续的m次的整体的前后都不是正面的吗

mathe

的确表达上有问题，感觉不就是投掷m次有正好最大x次朝上的概率吗？